Using kmp to store all the length of prefix and then dp

```java []
class Solution {
    Integer[] dp;
    public int minValidStrings(String[] words, String target) {
        int n = target.length();
       dp=new Integer[target.length()];
    //    Arrays.fill(dp, Integer.MAX_VALUE);
//dp[0] = 0;

        List<List<Integer>> matches = new ArrayList<>(n);
        for (int i = 0; i < n; i++) {
            matches.add(new ArrayList<>());
        }
        char[] targetChars = target.toCharArray();
        for (String word : words) {
            char[] wordChars = word.toCharArray();
            //System.out.println(words);
            int m = wordChars.length;
            int[] pi = new int[m];
            for (int i = 1, j = 0; i < m; i++) {
                while (j > 0 && wordChars[i] != wordChars[j]) {
                    j = pi[j - 1];
                }
                if (wordChars[i] == wordChars[j]) {
                    j++;
                }
                pi[i] = j;
            }

            for (int i = 0, j = 0; i < n; i++) {
                while (j > 0 && targetChars[i] != wordChars[j]) {
                    j = pi[j - 1];
                }
                if (targetChars[i] == wordChars[j]) {
                    j++;
                }
                if (j > 0) {
                    matches.get(i - j + 1).add(j);
                    if (j == m) {
                        j = pi[j - 1]; 
                    }
                }
            }
          
        }
     
        int ans=f(0,matches,words);
        if(ans>=Integer.MAX_VALUE/10)return -1;
        return ans;
    }
    public int f(int idx,List<List<Integer>> matches,String[]words){
       if(idx>=matches.size())return 0;
      if(dp[idx]!=null)return dp[idx];
        int ans=Integer.MAX_VALUE/10;
        for(int len:matches.get(idx)){
           ans=Math.min(ans,1+f(idx+len,matches,words));
        }
    //    ans=Math.min(ans,f(idx+1,matches));
        return dp[idx]=ans;

    }
}
```
['Java']