[Python3] Z-function + BFS
Intuition\nIf for each $i$ we know the "longest jump" we can make s.t. $\text{target}[i:i+\text{longest\_jump}] == \text{prefix of some word}$ then it\'s a grap
# Intuition\nIf for each $i$ we know the "longest jump" we can make s.t. $\\text{target}[i:i+\\text{longest\\_jump}] == \\text{prefix of some word}$ then it\'s a graph problem where each $i$ is a node and there is an edge from $i$ to each of $[i+1, \\text{longest\\_jump}]$ nodes\n\n# Approach\n\n* Calculate the "longest jumps" efficiently using z-function\n* Calculate the shortest path using BFS\n\n# Complexity\n- Time complexity: $$ ( len(\\text{words}) \\times (\\text{max\\_word\\_length}+len(\\text{target})) ) $$\n\n- Space complexity: $$ sizeof(\\text{words}) + sizeof(\\text{target}) $$\n\n# Code\n```python3 []\n# https://cp-algorithms.com/string/z-function.html\n"""\nz_function returns an array of size len(s):\narray[i] = max(sz) s.t. s[:sz] == s[i:i+sz]\n"""\ndef 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[i + z[i]] == s[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\nclass Solution:\n    def minValidStrings(self, words: List[str], target: str) -> int:\n        n = len(target)\n\n        # z function \u2014 O( len(words) x (max_word_length+len(target)) )\n        # maxjump[i] = max(j) s.t. target[i:j] is a prefix of some word\n        maxjump = [i for i in range(n)]\n        for w in words:\n            z = z_function(w + "$" + target)\n            for i in range(n):\n                maxjump[i] = max(maxjump[i], i + z[len(w) + 1 + i])\n\n        # bfs \u2014 O( len(target) )\n        q = [0]\n        maxseen = 0\n        step = 0\n        while len(q) > 0:\n            newq = []\n            for i in q:\n                for j in range(maxseen + 1, maxjump[i] + 1):\n                    if j == len(target):\n                        return step + 1\n                    newq.append(j)\n                    maxseen = j\n            step += 1\n            q = newq\n        return -1\n\n```
['Python3']