<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>

'''
min # of valid strings to form target 1

you are given an array of strings WORDS and a string TARGET
a string X is called valid if X is a prefix of any string in words

return the minimum # of valid strings that can be concatenated to form target,
    if it is not possible to form target return -1


EX 1:
    words = ["abc","aaaaa","bcdef"] target = "aabcdabc"
    output = 3
    take [aa] from string[1]
    take [bcd] from string[2]
    take [abc] from string[0]

EX 2:
    words = ["abababab","ab"], target = "ababaababa"
    ouptut = 2
    take [ababa] from string[0]
    take [ababa] from string[0]


doesnt matter what order of the strings we get it from, we just want the prefixes that match what we need

im thinking maybe we sort our words list?
then we can go thru and find how many of the word fits what we need,
    what if what we need is in a different string?
    we can use binary search to find what string start we need?
    we want the MINIMUM of string prefix used.
        SOOO we want to use the most amount of letters possible from one word
        we can reuse words
        as long as prefix's match

could we use a trie?
traverse trie as deep as possible
once end is reached increment by 1
restart at start of trie
'''
# class Node:
#     def __init__(self, next_letters=dict()):
#         self.next_letters = next_letters

class Solution:
    def minValidStrings(self, words: List[str], target: str) -> int:
        root = dict()
        n = len(target)
        dp = [-1] * n
        count = 0
        i = 0

        for word in words:
            temp = root
            for char in word:
                if char not in temp:
                    temp[char] = dict()
                    temp = temp[char]
                else:
                    temp = temp[char]

        def dfs(i):
            if i == n:
                return 0
            if dp[i] != -1:
                return dp[i]
            
            res = float('inf')
            cur = root
            for j in range(i, n):
                if target[j] not in cur:
                    break
                cur = cur[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

42948