[Python 3] string hashing + greedy / sliding window, <400ms O(m+n) linear time / space
Intuition\n Describe your first thoughts on how to solve this problem. \nThis is similar to a frog jumping forward in a sequence of stones. At the beginning, th
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThis is similar to a frog jumping forward in a sequence of stones. At the beginning, the frog is on `target[0]`, and it can jump from `i` to `j` if `target[i:j]` is valid. Also, it\'s easy to prove that the minimum step to reach `target[i]` is non-decreasing. Then, we only need to test the farthest letter it can reach in each step, and we get the answer when it reaches the end.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nFirst, we should know that hashing a string costs linear time to it\'s length, and the hash value of it\'s substring can be calculated in $O(1)$ time similar to the prefix sum technique. We store the hash of all prefix of words (valid strings) in a set, and also store the hash of all prefix of target in a list.\n\nThen, we can start "jumping". In each round `i`, `range(frm, to)` means the indices it can reach with at least `i` jumps. Since the farthest position with `i` jumps is monotinic, we can use a sliding window as the range of substring for each valid test, which ensures linear time complexity.\n\n# Complexity\n`m = sum(words[i].length), n = target.length`\n- Time complexity:\n  $O(m+n)$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:\n  $O(m+n)$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```python3 []\n# pre-calculate all pow(B, i, M) with linear time\nB = 131\nM = 212370440130137957\nPBM = []\nh = 1\nfor i in range(60_000):\n    PBM.append(h)\n    h = h * B % M\n\nclass Solution:\n    def minValidStrings(self, words: List[str], target: str) -> int:\n        # Calculate hash from left to right\n        # Example: hash(\'abc\') = (a * B ** 2 + b * B **1 + c * B ** 0) % M\n        # Suffix hash: hash(s2) = (hash(s1 + s2) - hash(s1) * B ** len(s2)) % M\n        valid_h = set()\n        for w in words:\n            h = 0\n            for c in w:\n                h = (h * B + ord(c)) % M\n                valid_h.add(h)\n        \n        target_h = [0]  # Exclusive indexing: target_h[i] = hash(target[:i])\n        h = 0\n        for c in target:\n            h = (h * B + ord(c)) % M\n            target_h.append(h)\n            \n        def has_sub(l, r):  # test whether target[l:r] is valid\n            return (target_h[r] - target_h[l] * PBM[r - l]) % M in valid_h\n\n        frm, to = 0, 1  # First str must start with target[0:1]\n        n = len(target)\n        for ans in count(1):\n            new_to = to\n            for i in range(frm, to):\n                # If target[:x] can be matched, next string can start with target[x],\n                # or in other words, the right boundary of next round can be x + 1\n                while has_sub(i, new_to):\n                    if new_to == n:\n                        return ans\n                    new_to += 1\n            if new_to == to:  # no update means failed\n                return -1\n            frm, to = to, new_to\n      \n```
['Python3']