Simple KMP Algorithm + DP || LPS Array || Beats 100%
Complexity\n- Time complexity:O(nm)\n Add your time complexity here, e.g. O(n) \n\n- Space complexity:O(n|words|+m)\n Add your space complexity here, e.g. O(n) 
# Complexity\n- Time complexity:$$O(n*m)$$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:$$O(n*|words|+m)$$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```cpp []\nclass Solution {\npublic:\n    vector<int> LPS(string& s){\n        int n = s.size();\n        vector<int> lps(n, 0);\n        int i = 1, prev = 0;\n        while(i < n){\n            if(s[i] == s[prev]){\n                prev++;\n                lps[i] = prev;\n                i++;\n            }else{\n                if(prev > 0){\n                    prev = lps[prev-1];\n                }else{\n                    lps[i] = 0;\n                    i++;\n                }\n            }\n        }\n        return lps;\n    }\n    vector <int> search(string p, string t)\n    {\n        string ns = p + "#" + t;\n        vector<int> lps = LPS(ns);\n        vector<int> ans;\n        int n = p.size();\n        for(int i=n+1; i<lps.size(); i++){\n            ans.push_back(i-n-lps[i]);\n        }\n        return ans;\n    }\n    int minValidStrings(vector<string>& w, string t) {\n        int n = w.size();\n        vector<vector<int>> arr(n);\n        for(int i=0; i<n; i++){\n            arr[i] = search(w[i], t);\n        }\n        int m = t.size();\n        vector<int> dp(m+1, 1e9);\n        dp[0] = 0;\n        for(int i=0; i<m; i++){\n            for(int j=0; j<n; j++){\n                dp[i+1] = min(dp[i+1], dp[arr[j][i]] + 1);\n            }\n        }\n        if(dp[m] == 1e9) return -1;\n        return dp[m];\n    }\n};\n```
['C++']