3292. Minimum Number of Valid Strings to Form Target II
\n# Code\njava []\nclass Solution {\n    public int minValidStrings(String[] words, String target) {\n        int n = target.length();\n        int[] dp = new i
\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```
['Dynamic Programming', 'Java']