Aho-Corasick 35 lines
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 []\nclass Trie:\n    def __init__(self):\n        self.c=defaultdict(Trie)\n        self.i=0\n        self.prev=None\n    def add(self, w):\n        cur=self\n        for i,ch in enumerate(w):\n            cur=cur.c[ch]\n            cur.i=i+1\n    def next(self, ch):\n        if ch in self.c: return self.c[ch]\n        if not self.prev: return self\n        return self.prev.next(ch)\n    def aho_corasick(self):\n        dq=deque((self, y) for y in self.c.values())\n        while dq:\n            x,y = dq.popleft()\n            y.prev=x\n            for ch in y.c: dq.append((x.next(ch), y.c[ch]))\nclass Solution:\n    def minValidStrings(self, words: List[str], target: str) -> int:\n        trie=Trie()\n        for w in words: trie.add(w)\n        trie.aho_corasick()\n        n=len(target)\n        pre=[0]*n\n        for i,ch in enumerate(target):\n            trie=trie.next(ch)\n            pre[i]=trie.i\n        res,i=0, n-1\n        while i>=0:\n            if pre[i]==0: return -1\n            res,i=res+1, i-pre[i]\n        return res\n        \n```
['Python3']