Python 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(m*n) # m: len(words), n: len(target)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:O(m+n)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```python3 []\nclass Solution:\n    def minValidStrings(self, words: List[str], target: str) -> int:\n        #KMP \n        #idea: picking up the longest suffix of target in prefix of words will get the minimum number of valid prefixes\n        n = len(target)\n        dp = [0]*n #store the longest length of suffix until i\n        ans = 0\n        def create_LPS(s):\n            m = len(s)\n            LPS = [0]*m\n            l, r = 0, 1\n            while r < m:\n                if s[l] == s[r]:\n                    l += 1\n                    LPS[r] = l\n                    r += 1\n                else:\n                    if l == 0:\n                        r += 1\n                    else:\n                        l = LPS[l-1]\n            return LPS\n\n        for word in words:\n            l_w = len(word)\n            LPS = create_LPS(word+\'#\'+target)\n            for i in range(n):\n                dp[i] = max(dp[i], LPS[l_w+1+i])\n        #print(dp)\n        length = n\n        while length > 0 and dp[length-1] > 0:\n            ans += 1\n            length -= dp[length-1]\n        return ans if length == 0 else -1\n```
['Python3']