[Python3] KMP + Greedy O(M*N + M*K) FULL EXPLANATION W/ Proof
Intuition\n Describe your first thoughts on how to solve this problem. \n\nApplying two formal proofs of contradiction lead us to our greedy solution: Take the 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\nApplying two formal proofs of contradiction lead us to our greedy solution: Take the maximum amount of steps that we can at any given step. This is a loose proof, but the main ideas of the proofs are below.\n\n\n**Proof of Optimality & Correctness:**\n(This is best seen with a visualization, and in the following explanation assume we are traversing the array from right to left)\n\nAssume there was some solution that decides to take a shorter prefix step than the maximum possible at a given index. Our greedy algorithm with take one step from index i to index X. The "optimal" algorithm takes a smaller step from index i to index Y > X. \n\n**Case 1)** From index X, we can\'t take any steps backward. \n\nOur greedy algorithm will reach index X and return -1, since we we can\'t construct the target string. Supposedly, the "optimal" solution is able to reach end from a larger index. However, any solution that reaches the end, will use the prefix arr[:X]. We assumed there is no prefix arr[:X], because our initial assumption was that there was no solution and that we can\'t take any steps backward. This is a proof by contradiction, therefore our algorithm will find a solution.\n\nNow we show that our algorithm produces the optimal solution.\n\n**Case 2)** From index X, we can take steps backwards, and assume that both greedy and optimal algorithms find a solution (from case 1). \n\nAssume that we can reach the final index (or any index before X) in fewer steps by taking a step to index Y > X (taking a smaller than maximum jump). Our greedy algorithm reaches index X in one step. The "optimal algorithm" must take a series of steps to overcome the path in index X. However, the "optimal" algorithm will reach index X at some point in the solution. It will "pass by" index X in 2 or greater steps. If the greedy solution simply "followed" this optimal solution, because any prefix in arr[:X] is of course available for both algorithms, by immediately taking a step and ending and starting at the same positions as the "optimal" algorithm, the greedy algorithm would reach the final index in fewer or equal steps than the optimal algorithm, no matter what. Therefore, our "optimal" solution can never do better than our greedy solution. \n\nNote that this problem structure is unique, and lends itself to a greedy solution. However, other similar problem such as Word Break (LC 139), must consider every possible starting word at every index, since we cannot be greedy. Taking a smaller word might lead to a correct solution, because taking a larger word might not lead to matching a smaller word earlier on. At each index, we don\'t have the same set of choices across all words. As in, we don\'t have the choice of just choosing prefixes.\n\nIt is extremely unique and at first slightly non-intuitive why this is the case, but after thinking about this problem for a while, having the choice to take prefixes of words at every single index lends us to a greedy solution. If we couldn\'t take prefixes of words, and instead had to take whole words, then this would become Word Break which needs DP.\n\n\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nDefine a KMP helper function, I highly suggest watching Neetcode\'s video on find the first occurence in string problem if you have never seen the KMP algorithm before. If you haven\'t seen the KMP algorithm before, this problem is likely not the best instroduction to it. \n\nThe KMP algorithm produces a "suffix" table after we have matched our pattern lps data structure with our target string. This "suffix" table tell us how many steps before the current index match a prefix available to us. And this is exactly what we need. We consider the maximum steps or maximum jump that we can take at each index across all words, and go for it. If we ever reach a point where we can\'t jump, then we return -1. The proof for this case is above.\n# Complexity\n- Time complexity: O(M*(N+K))\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\nM represents the # of words\nK is the longest length of a word in words\nN is the length of the target string\n\n- Space complexity: O(N + K)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nThis is for the LPS and suffix tables.\n\n# Code\n```python3 []\nclass Solution:\n    def minValidStrings(self, words: List[str], target: str) -> int:\n        def kmp(pattern, target):\n            n, m = len(pattern), len(target)\n            lps = [0]*n\n            j,i = 0,1\n            while i < n:\n                while j and pattern[j] != pattern[i]:\n                    j = lps[j-1]\n                if pattern[j] == pattern[i]:\n                    j += 1\n                    lps[i] = j\n                else:\n                    lps[i] = 0\n                i += 1\n\n            res = [0]*m\n            i,j = 0,0\n            while i < m:\n                while j and (j == n or pattern[j] != target[i]):\n                    j = lps[j-1]\n                if pattern[j] == target[i]:\n                    j += 1\n                    res[i] = j\n                else:\n                    res[i] = 0\n                i += 1\n            return res\n        \n        m = len(target)\n        option = [0]*m\n        for word in words:\n            arr = kmp(word, target)\n            for i,j in enumerate(arr):\n                option[i] = max(option[i], j)\n        i = m-1\n        steps = 0\n        while i > -1:\n            if option[i] == 0:\n                return -1\n            i -= option[i]\n            steps += 1\n        return steps\n        \n        \n            \n```
['Python3']