[Python3] kmp + dp
\npython\nclass Solution:\n    def minValidStrings(self, words: List[str], target: str) -> int:\n        n = len(target)\n        vals = [set() for _ in range(n
\n```python\nclass Solution:\n    def minValidStrings(self, words: List[str], target: str) -> int:\n        n = len(target)\n        vals = [set() for _ in range(n)]\n        \n        def kmp(pattern, text):\n            k = 0\n            lps = [0] \n            for i in range(1, len(pattern)):\n                while k and pattern[k] != pattern[i]: k = lps[k-1]\n                if pattern[k] == pattern[i]: k += 1\n                lps.append(k)\n            k = 0\n            ans = []\n            for i, ch in enumerate(text): \n                while k and (k == len(pattern) or pattern[k] != ch): k = lps[k-1]\n                if pattern[k] == ch: k += 1\n                ans.append(k)\n            return ans\n\n        for word in words: \n            cand = kmp(word, target)\n            for i, k in enumerate(cand): \n                if k: vals[i].add(k)\n        dp = [inf]*(n+1)\n        dp[n] = 0 \n        for i in range(n-1, -1, -1): \n            for k in vals[i]:\n                dp[i-k+1] = min(dp[i-k+1], 1 + dp[i+1])\n        return dp[0] if dp[0] < inf else -1\n```\n\nAdding solution via Aho-Corasick algo \n```\nclass AhoCorasick:\n    def __init__(self):\n        self.root = {"parent": None, "suffix": None, "$": 0}\n        \n    def build(self, patterns: List[str]): \n        for pattern in patterns:\n            node = self.root\n            size = 0\n            for ch in pattern:\n                if ch not in node: node[ch] = {"parent": node}\n                node = node[ch]\n                size += 1\n                node["$"] = size\n        queue = deque([self.root])\n        while queue:\n            for _ in range(len(queue)):\n                node = queue.popleft()\n                for ch, child in node.items():\n                    if ch not in ("parent", "suffix", "$"): \n                        suffix = node["suffix"]\n                        while suffix and ch not in suffix: suffix = suffix["suffix"]\n                        if suffix: child["suffix"] = suffix[ch]\n                        else: child["suffix"] = self.root\n                        queue.append(child)\n\n    def match(self, text: str):\n        ans = []\n        node = self.root\n        for ch in text:\n            while ch not in node and node["suffix"]:\n                node = node["suffix"]\n            if ch in node: node = node[ch]\n            ans.append(node["$"])\n        return ans \n    \n\nclass Solution:\n    def minValidStrings(self, words: List[str], target: str) -> int:\n        n = len(target)\n        trie = AhoCorasick()\n        trie.build(words)\n        dp = [inf]*(n+1)\n        dp[n] = 0\n        for i, x in reversed(list(enumerate(trie.match(target)))):\n            if x == 0: return -1 \n            dp[i+1-x] = min(dp[i+1-x], dp[i+1] + 1)\n        return dp[0] \n```
['Python3']