Aho Corsack | Python 3
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)$$ -->\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```python3 []\nfrom typing import List\nfrom collections import deque\n\n\ndef to_idx(s: str):\n    return ord(s) - ord("a")\n\n\nclass Trie:\n    def __init__(self, depth=0):\n        self.is_end = False\n        self.depth = depth\n        self.stored_words = []  # added for quick recovery of what this trie represents\n        self.d = [None for _ in range(26)]\n        self.failure_to = None  # added for aho corasick\n\n    def insert(self, string: str, idx: int):\n        if idx == len(string):\n            self.is_end = True\n            self.stored_words.append(string)\n        else:\n            tmp = to_idx(string[idx])\n            if self.d[tmp] is None:\n                self.d[tmp] = Trie(self.depth + 1)\n            self.d[tmp].insert(string, idx + 1)\n\n    def __str__(self):\n        return str(self.d) + str(self.is_end) + str(self.stored_words)\n\n\nclass Solution:\n    def minValidStrings(self, words: List[str], target: str) -> int:\n        # trie\n        t = Trie()\n        for word in words:\n            t.insert(word, 0)\n        # aho corasick\n        # build failure graph\n        # start with everything connected to root\n        q = deque()\n        for i in range(len(t.d)):\n            if t.d[i] is not None:  # this is a valid connection\n                # first, set the node to fail towards the root\n                t.d[i].failure_to = t  # fail to root\n                q.append(t.d[i])  # explore it soon\n        # also set root to loop back to itself to prevent infinite recursion\n        # when trying to look for a success\n        for i in range(len(t.d)):\n            if t.d[i] is None:\n                t.d[i] = t\n\n        # then, just bfs\n        while len(q) > 0:\n            subtree = q.popleft()\n\n            for i in range(len(subtree.d)):\n                if subtree.d[i] is not None:  # is a valid connection\n                    # add it to the queue\n                    q.append(subtree.d[i])\n\n                    # figure out where this new node should fail to\n                    # by exploring until something succeeds\n                    tmp = subtree.failure_to\n                    while tmp.d[i] is None:  # while this is still a failure, go back\n                        tmp = tmp.failure_to\n                    # finally, store this\n                    subtree.d[i].failure_to = tmp.d[i]\n                    # and store any words this may entail\n                    subtree.d[i].stored_words.extend(tmp.d[i].stored_words)\n\n        # min times[i] = min_times to create a length i string\n        min_times = [float("inf") for _ in range(len(target) + 1)]\n        min_times[0] = 0  # length 0 costs 0\n        cur = t\n        for i in range(1, len(target) + 1):\n            # advance to next state\n            tmp = cur.d[to_idx(target[i - 1])]\n            if tmp is not None:\n                cur = tmp\n            else:\n                while cur.failure_to.d[to_idx(target[i - 1])] is None:\n                    cur = cur.failure_to\n                cur = cur.failure_to.d[to_idx(target[i - 1])]\n\n            # just use the depth\n            min_times[i] = min_times[i - cur.depth] + 1\n            # print("at", target[i - 1], "have depth", cur.depth)\n            # for el in cur.stored_words:\n            #     print(el, "depth", cur.depth)\n\n        if min_times[-1] == float("inf"):\n            return -1\n        return min_times[-1]\n\n\n```
['Python3']