Z function + jump game ii
Approach\nWe have a target string and a list of words. We want to find the length of the maximum prefix match in our given words and the substring starting here
# Approach\nWe have a target string and a list of words. We want to find the length of the maximum prefix match in our given words and the substring starting here `target[i:]`. If we have the maximum prefix match array then this problem reduces to [Jump game II](https://leetcode.com/problems/jump-game-ii/description/).\n\nFor [part 1](https://leetcode.com/problems/minimum-number-of-valid-strings-to-form-target-i/description/) of this problem, we can build a `trie` from our list of words and do a maximum possible trie matching at every index. This `trie` approach is too slow for this problem. A more efficient way to calculate this is via [Z-functions](https://cp-algorithms.com/string/z-function.html).\n\nFinally we find the minimum number of valid strings (or minimum jumps till end) using a greedy 1D BFS approach. For more details about this check this [solution](https://leetcode.com/problems/jump-game-ii/solutions/18014/concise-o-n-one-loop-java-solution-based-on-greedy/) or this [video](https://www.youtube.com/watch?v=dJ7sWiOoK7g&ab_channel=NeetCode).\n\n\n# Complexity\nTime complexity:\n - Z-function is linear with input. But we call it once per word.\n`O(m * (n + w))` where n = len(target), m = num words, w = avg. word length\n\n - 1D BFS is linear 1 pass.\n`O(n)`\n\nSpace complexity:\n`O(n + w)` for Z-function and `O(n)` for dp array.\n\n# Code\n```python3 []\nclass Solution:\n    def minValidStrings(self, words: List[str], target: str) -> int:\n        \n        def Z_function(s):\n            n = len(s)\n            Z = [0] * n\n            l = r = 0\n            for i in range(1, n):\n                if i < r:\n                    Z[i] = min(Z[i - l], r - i)\n                while i + Z[i] < n and s[Z[i]] == s[i + Z[i]]:\n                    Z[i] += 1\n                if i + Z[i] > r:\n                    l = i\n                    r = i + Z[i]\n            return Z\n        \n        n = len(target)\n        dp = [0] * n\n        for word in words:\n            Z_arr = Z_function(word + \'#\' + target)\n            offset = len(word) + 1\n            for i in range(n):\n                dp[i] = max(dp[i], Z_arr[i + offset])\n\n        l = r = 0\n        hops = 0\n        while r < n:\n            max_reach = 0\n            for i in range(l, r + 1):\n                max_reach = max(max_reach, i + dp[i])\n            if max_reach == 0: # we cannot go further\n                return -1\n            l = r + 1\n            r = max_reach\n            hops += 1\n        return hops\n        \n```
['Dynamic Programming', 'Breadth-First Search', 'String Matching', 'Python3']