KMP + BFS
\nclass Solution:\n    def minValidStrings(self, words: List[str], target: str) -> int:\n  \n        def kmp(sub_s, s):\n            k, n, pref = 0, len(sub_s),
```\nclass Solution:\n    def minValidStrings(self, words: List[str], target: str) -> int:\n  \n        def kmp(sub_s, s):\n            k, n, pref = 0, len(sub_s), [0]\n            for i in range(1, n):\n                while k and sub_s[k] != sub_s[i]:\n                    k = pref[k-1]\n                if sub_s[k] == sub_s[i]:\n                    k += 1\n                pref.append(k)\n            k, ans = 0, []\n            for i, ch in enumerate(s):\n                while k and sub_s[k] != ch:\n                    k = pref[k-1]\n                if sub_s[k] == ch:\n                    k += 1 \n                ans.append(i-k+1)\n                if k == n:\n                    k = pref[k-1]\n            return ans\n\n        n, graph = len(target), defaultdict(set)\n        for word in words: \n            for v, u in enumerate(kmp(word, target), 1):\n                if u != v:\n                    graph[u].add(v)\n           \n        queue, visited = [0], [0] * n\n        step, visited[0] = 1, 1\n        while queue:\n            new_queue = []\n            for u in queue:\n                for v in graph[u]:\n                    if v == n:\n                        return step\n                    if not visited[v]:\n                        new_queue.append(v)\n                        visited[v] = 1\n            queue = new_queue\n            step += 1  \n        return -1  \n```
['Breadth-First Search', 'Python3']