<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 Trie:
    class TrieNode:
        def __init__(self):
            self.children = [None] * 26

    def __init__(self):
        self.root = Trie.TrieNode()

    def insert(self, word):
        curr = self.root
        for ch in word:
            ch = ord(ch) - ord("a")
            if not curr.children[ch]:
                curr.children[ch] = Trie.TrieNode()
            curr = curr.children[ch]
        # end for


class Solution:
    def minValidStrings(self, words: List[str], target: str) -> int:
        trie = Trie()
        for word in words:
            trie.insert(word)
        # end for
        n = len(target)
        INF = n * 2

        # dp[i]: min number of words for target[i:]
        dp = [INF] * (n + 1)

        # B.C.
        dp[n] = 0

        for i in range(n - 1, -1, -1):
            curr = trie.root
            # prefix will be target[i:j+1]
            for j in range(i, n):
                ch = ord(target[j]) - ord("a")
                if not curr.children[ch]:
                    break
                curr = curr.children[ch]
                dp[i] = min(dp[i], 1 + dp[j + 1])
            # end for
        # end for
        return dp[0] if dp[0] != INF else -1


# class TrieNode:
#     def __init__(self):
#         self.children = [None for _ in range(26)]

#     def contains(self, word, i, j) -> bool:
#         if i == j:
#             return True
#         if not self.children[ord(word[i]) - ord('a')]:
#             return False
#         return self.children[ord(word[i]) - ord('a')].contains(word, i + 1, j)

#     def containsSubstr(self, substr, i=0) -> bool:
#         if i == len(substr):
#             return True
#         if not self.children[ord(substr[i]) - ord('a')]:
#             return False
#         return self.children[ord(substr[i]) - ord('a')].containsSubstr(substr, i + 1)


#     def add_word(self, word, i=0):
#         if i == len(word):
#             return
#         if not self.children[ord(word[i]) - ord('a')]:
#             self.children[ord(word[i]) - ord('a')] = TrieNode()
#         self.children[ord(word[i]) - ord('a')].add_word(word, i + 1)

# class Solution:
#     def minValidStrings(self, words: List[str], target: str) -> int:
#         n = len(target)
#         INF = n + 2
#         # min substring to form fist x chars in target
#         dp = [INF for _ in range(n + 1)]
#         dp[0] = 0

#         # dp[x] = min(target[... + prefix of word] + dp[x - prefix len])
#         # try all possible prefix
#         trie_root = TrieNode()

#         for word in words:
#             trie_root.add_word(word)

#         for length in range(1, n + 1):
#             # try all prev string
#             # print(f"length is {length}")
#             for i in range(0, length):
#                 j = length

#                 if dp[length - (j - i)] >= INF:
#                     continue

#                 # flag = trie_root.containsSubstr(target, i, j)
#                 flag = trie_root.containsSubstr(target[i:j])
#                 # in_str = "is in trie" if flag else "not in tree"
#                 # print(f"prefix is {target[i:j]} | {in_str}")
#                 if flag:
#                     dp[length] = min(dp[length], 1 + dp[length - (j - i)])
#             # end for
#         # end for

#         if dp[n] == INF:
#             return -1
#         return dp[n]

38549