[Python3/ C++] KMP + Greedy - Simple Solutions
Intuition\n- Inspired from this post\n Describe your first thoughts on how to solve this problem. \n\n# Approach\n Describe your approach to solving the problem
# Intuition\n- Inspired from this [post](https://leetcode.com/problems/minimum-number-of-valid-strings-to-form-target-ii/solutions/5788346/kmp/)\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:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n##### 1. KMP + Greedy\n```python3 []\nclass Solution:\n    def minValidStrings(self, words: List[str], target: str) -> int:\n        def prefix_function(s: str) -> List[int]:\n            n = len(s)\n            lps = [0 for _ in range(n)]\n            for i in range(1, n):\n                j = lps[i - 1]\n                while j > 0 and s[i] != s[j]: j = lps[j - 1]\n                if s[i] == s[j]: j += 1\n                lps[i] = j\n            return lps\n        \n        l = len(target)\n        ps = [0 for _ in range(l + 1)]\n        for word in words:\n            lps = prefix_function(word + "#" + target)\n            for i in range(1, l + 1):\n                ps[i] = max(ps[i], lps[len(word) + i])\n        res = 0\n        while l and ps[l]:\n            l -= ps[l]\n            res += 1\n        return res if l == 0 else -1\n```\n```C++ []\nvector<int> prefix_function(const string &s) {\n    int n = (int)s.length();\n    vector<int> pi(n);\n    for (int i = 1; i < n; i++) {\n        int j = pi[i-1];\n        while (j > 0 && s[i] != s[j])\n            j = pi[j-1];\n        if (s[i] == s[j])\n            j++;\n        pi[i] = j;\n    }\n    return pi;\n}    \nint minValidStrings(vector<string>& words, string target) {\n    vector<int> ps(target.size() + 1);\n    for (const auto &w : words) {\n        auto pi = prefix_function(w + "#" + target);\n        for (int i = 1; i <= target.size(); ++i)\n            ps[i] = max(ps[i], pi[w.size() + i]);\n    }\n    int len = target.size(), res = 0;\n    for (; len && ps[len]; ++res)\n        len -= ps[len];\n    return len == 0 ? res : -1;\n}\n```
['Array', 'String', 'Python3']