<p>You are given an array of strings <code>words</code> and a string <code>target</code>.</p>

<p>A string <code>x</code> is called <strong>valid</strong> if <code>x</code> is a <span data-keyword="string-prefix">prefix</span> of <strong>any</strong> string in <code>words</code>.</p>

<p>Return the <strong>minimum</strong> number of <strong>valid</strong> strings that can be <em>concatenated</em> to form <code>target</code>. If it is <strong>not</strong> possible to form <code>target</code>, return <code>-1</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">words = [&quot;abc&quot;,&quot;aaaaa&quot;,&quot;bcdef&quot;], target = &quot;aabcdabc&quot;</span></p>

<p><strong>Output:</strong> <span class="example-io">3</span></p>

<p><strong>Explanation:</strong></p>

<p>The target string can be formed by concatenating:</p>

<ul>
	<li>Prefix of length 2 of <code>words[1]</code>, i.e. <code>&quot;aa&quot;</code>.</li>
	<li>Prefix of length 3 of <code>words[2]</code>, i.e. <code>&quot;bcd&quot;</code>.</li>
	<li>Prefix of length 3 of <code>words[0]</code>, i.e. <code>&quot;abc&quot;</code>.</li>
</ul>
</div>

<p><strong class="example">Example 2:</strong></p>

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">words = [&quot;abababab&quot;,&quot;ab&quot;], target = &quot;ababaababa&quot;</span></p>

<p><strong>Output:</strong> <span class="example-io">2</span></p>

<p><strong>Explanation:</strong></p>

<p>The target string can be formed by concatenating:</p>

<ul>
	<li>Prefix of length 5 of <code>words[0]</code>, i.e. <code>&quot;ababa&quot;</code>.</li>
	<li>Prefix of length 5 of <code>words[0]</code>, i.e. <code>&quot;ababa&quot;</code>.</li>
</ul>
</div>

<p><strong class="example">Example 3:</strong></p>

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">words = [&quot;abcdef&quot;], target = &quot;xyz&quot;</span></p>

<p><strong>Output:</strong> <span class="example-io">-1</span></p>
</div>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= words.length &lt;= 100</code></li>
	<li><code>1 &lt;= words[i].length &lt;= 5 * 10<sup>3</sup></code></li>
	<li>The input is generated such that <code>sum(words[i].length) &lt;= 10<sup>5</sup></code>.</li>
	<li><code>words[i]</code> consists only of lowercase English letters.</li>
	<li><code>1 &lt;= target.length &lt;= 5 * 10<sup>3</sup></code></li>
	<li><code>target</code> consists only of lowercase English letters.</li>
</ul>

class Solution:
    def minValidStrings(self, words: List[str], target: str) -> int:
        n = len(target)
        vals = [set() for _ in range(n)]
        
        def kmp(pattern, text):
            k = 0
            lps = [0] 
            for i in range(1, len(pattern)):
                while k and pattern[k] != pattern[i]: k = lps[k-1]
                if pattern[k] == pattern[i]: k += 1
                lps.append(k)
            k = 0
            ans = []
            for i, ch in enumerate(text): 
                while k and (k == len(pattern) or pattern[k] != ch): k = lps[k-1]
                if pattern[k] == ch: k += 1
                ans.append(k)
            return ans

        for word in words: 
            cand = kmp(word, target)
            for i, k in enumerate(cand): 
                if k: vals[i].add(k)
        dp = [inf]*(n+1)
        dp[n] = 0 
        for i in range(n-1, -1, -1): 
            for k in vals[i]:
                dp[i-k+1] = min(dp[i-k+1], 1 + dp[i+1])
        return dp[0] if dp[0] < inf else -1
# class Solution:
#     def minValidStrings(self, words: List[str], target: str) -> int:
#         trie = Trie()
#         for w in words:
#             trie.insert(w)
        
#         n = len(target)

#         dp = [-1] * n
        
#         def dfs(i):
#             if i == n:
#                 return 0 
#             if dp[i] != -1:
#                 return dp[i] 
            
#             res = float('inf') 
#             cur = trie
#             for j in range(i, n):
#                 if target[j] not in cur.children:
#                     break
#                 cur = cur.children[target[j]]
#                 res = min(res, 1 + dfs(j + 1)) 
            
#             dp[i] = res
#             return res
        
#         result = dfs(0)
#         return result if result != float('inf') else -1

# class Trie:
#     def __init__(self):
#         self.children = {}

#     def insert(self, s):
#         cur = self
#         for c in s:
#             if c not in cur.children:
#                 cur.children[c] = Trie()
#             cur = cur.children[c]

# class Solution:
#     def minValidStrings(self, words: List[str], target: str) -> int:
#         trie = {}
#         for word in words: 
#             node = trie
#             for ch in word: 
#                 node = node.setdefault(ch, {})
#             node["#"] = word 
#         n = len(target) 
#         dp = [inf]*(n+1)
#         dp[n] = 0 
#         for i in range(n-1, -1, -1):
#             node = trie
#             for j in range(i, n):
#                 if target[j] in node: node = node[target[j]]
#                 else: break 
#                 dp[i] = min(dp[i], 1 + dp[j+1])
#         return dp[0] if dp[0] < inf else -1 

# class TrieNode:
#     def __init__(self):
#         self.childs=[None]*26
# class Trie:
#     def __init__(self):
#         self.root=TrieNode()
        
#     def insert(self,word):
#         temp=self.root
#         for i in word:
#             idx=ord(i)-ord('a')
#             if temp.childs[idx]==None:
#                 temp.childs[idx]=TrieNode()
#             temp=temp.childs[idx]
                
# class Solution:
#     def __init__(self):
#         self.dp=[]
#         self.n=0
#         self.target=""
    
#     def solve(self,i,root):
        
#         if i==self.n:#mis 0
#             return 0
#         if self.dp[i]!=-1:
#             return self.dp[i]
#         temp=root
#         res=float('inf')
#         for j in range(i,self.n):
#             idx=ord(self.target[j])-ord('a')#MISTAKE 1
#             if temp.childs[idx]==None:
#                 break
#             temp=temp.childs[idx]
#             t=self.solve(j+1,root)
#             if t != float('inf'):
#                 res=min(res,t+1) # MISTAKE 2
#         self.dp[i]=res
#         return res
        
#     def minValidStrings(self,words,target):
#         t=Trie()
#         for i in words:
#             t.insert(i)
#         self.n=len(target)
#         self.dp=[-1]*(self.n)
#         self.target=target
#         res=self.solve(0,t.root)
#         # print(t)
#         return -1 if res == float('inf') else res 
    
26330