Easy Java Solution | Beginner Friendly
Intuition\nTo solve the problem of finding the minimum number of valid strings required to construct a target string, we need to determine how each word from th
# Intuition\nTo solve the problem of finding the minimum number of valid strings required to construct a target string, we need to determine how each word from the list can contribute to forming the target. The goal is to efficiently track the minimum number of words needed through dynamic programming (DP). The problem essentially boils down to a variant of the "minimum number of coins" problem, where the "coins" are the valid strings and the "amount" is the target string.\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n1. Preprocessing Matches:\n\n- For each word in the list, use the Knuth-Morris-Pratt (KMP) algorithm to determine all the positions in the target string where each word can match.\n- This preprocessing will help us quickly find where each word can be placed within the target string.\n2. Dynamic Programming (DP) Table:\n- Use a DP array where dp[i] represents the minimum number of words needed to form the substring target[0:i].\n- Initialize dp[0] = 0 because zero words are needed to form an empty string.\n- For each position i in the target, update the DP table based on the matches found during preprocessing. If a word can match starting at position i, update the DP value for the end of that match position.\n3. Result:\n\n- The value dp[n] (where n is the length of the target string) will give us the minimum number of words needed to form the entire target. If dp[n] remains as Integer.MAX_VALUE, it means it\u2019s impossible to form the target with the given words.\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n## Time complexity: $$O(m * n + n * k)$$,\nwhere:\n- $$O(m * n)$$ is the time complexity for preprocessing each word using the KMP algorithm, where m is the length of a word and n is the length of the target string.\n- $$O(n * k)$$ is the time complexity for updating the DP table, where k is the number of matches found for each position in the target.\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n## Space complexity: $$O(n + m * k)$$, \nwhere:\n- $$O(n)$$ is for the DP array.\n- $$O(m * k)$$ is for storing the matches found, where m is the length of the words and k is the number of matches.\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```java []\nclass Solution {\n    public int minValidStrings(String[] words, String target) {\n        int n = target.length();\n        int[] dp = new int[n + 1];\n        Arrays.fill(dp, Integer.MAX_VALUE);\n        dp[0] = 0;\n\n        List<List<Integer>> matches = new ArrayList<>(n);\n        for (int i = 0; i < n; i++) {\n            matches.add(new ArrayList<>());\n        }\n        char[] targetChars = target.toCharArray();\n        for (String word : words) {\n            char[] wordChars = word.toCharArray();\n            int m = wordChars.length;\n            int[] pi = new int[m];\n            for (int i = 1, j = 0; i < m; i++) {\n                while (j > 0 && wordChars[i] != wordChars[j]) {\n                    j = pi[j - 1];\n                }\n                if (wordChars[i] == wordChars[j]) {\n                    j++;\n                }\n                pi[i] = j;\n            }\n\n            for (int i = 0, j = 0; i < n; i++) {\n                while (j > 0 && targetChars[i] != wordChars[j]) {\n                    j = pi[j - 1];\n                }\n                if (targetChars[i] == wordChars[j]) {\n                    j++;\n                }\n                if (j > 0) {\n                    matches.get(i - j + 1).add(j);\n                    if (j == m) {\n                        j = pi[j - 1]; \n                    }\n                }\n            }\n        }\n        for (int i = 0; i < n; i++) {\n            if (dp[i] == Integer.MAX_VALUE) continue;\n            for (int len : matches.get(i)) {\n                if (i + len <= n) {\n                    dp[i + len] = Math.min(dp[i + len], dp[i] + 1);\n                }\n            }\n        }\n        return dp[n] == Integer.MAX_VALUE ? -1 : dp[n];\n    }\n}\n```
['Java']