Python || Rolling Hashing ||faster than 96%
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:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\no(N)\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\no(N)\n\n# Code\n```python3 []\nclass Solution:\n    def minValidStrings(self, words: List[str], target: str) -> int:\n        d, prime = 256,  1000000007\n        pow_d = [1] * (len(target) + 1)\n        for i in range(1, len(pow_d)):\n            pow_d[i] = (pow_d[i - 1] * d) % prime\n        h = set()\n        for i in words:\n            th = 0\n            for j in i:\n                th = (d * th + ord(j)) % prime\n                h.add(th)\n        dp = [math.inf] * len(target)\n        i = 0\n        th = 0\n        l = 0\n        while i < len(target):\n            th = (d * th + ord(target[i])) % prime\n            if th in h:\n                dp[i] = 1 + (dp[l - 1] if l - 1 >= 0 else 0)\n            else:\n                while l < i:\n                    temp = pow_d[i - l]\n                    th = (th - ord(target[l]) * temp) % prime\n                    l += 1\n                    if th in h:\n                        dp[i] = 1 + (dp[l - 1] if l - 1 >= 0 else 0)\n                        break\n            i += 1\n        return (dp[-1] if dp[-1] != math.inf else -1)\n\n\n\n\n            \n\n\n\n\n            \n```
['Array', 'String', 'Dynamic Programming', 'Rolling Hash', 'Python3']