Simple Clean Solution using KMP
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\n Describe your approach to solving the problem. \n\n# Complexity\n- Time 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity: O(n*m)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: ~O(n)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```cpp []\nclass Solution {\npublic:\n    int minValidStrings(vector<string>& words, string target) {\n        int len = target.length();\n        int n = words.size();\n        vector<vector<int>> lps(n);\n        for(int i=0;i<n;i++){\n            vector<int> temp(words[i].length()+len+1);\n            calcLps(temp,words[i]+\'#\'+target);\n            lps[i]=temp;\n        }\n        int ans=0;\n        while(len>0){\n            int jump = 0;\n            for(int i=0;i<words.size();i++){\n                int currIndex = words[i].length()+len;\n                jump=max(jump,lps[i][currIndex]);\n            }\n            ans++;\n            if(jump==0){\n                return -1;\n            }\n            len-=jump;\n        }\n        return ans;\n    }\n\n    void calcLps(vector<int>& ans,string pattern){\n        int len=0;\n        int i=1;\n        while(i<pattern.length()){\n            if(pattern[i]==pattern[len]){\n                len++;\n                ans[i]=len;\n                i++;\n            } else {\n                if(len==0){\n                    ans[i]=0;\n                    i++;\n                } else {\n                    len=ans[len-1];\n                }\n            }\n        }\n        return;\n    }\n};\n\n\n\n/*\n\na   a   b   c   d   a   b   c\ni\n\npattern : a\nlength: 1\n\n\n\n\n*/\n```
['Array', 'String', 'C++']