<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 TrieNode:
    def __init__(self):
        self.childs = {}

class Trie:
    def __init__(self):
        self.root = TrieNode()
    
    def addWord(self, w):
        cur = self.root
        for c in w:
            if c not in cur.childs:
                cur.childs[c] = TrieNode()
            
            cur = cur.childs[c]
    def prefixLen(self, s):
        cur = self.root
        n = len(s)
        ans = 0
        for i in range(n):
            c=s[i]
            if c in cur.childs:
                ans+=1
                cur = cur.childs[c]
            else:
                return ans
        return n # ans




class Solution:
    def minValidStrings(self, words: List[str], target: str) -> int:
        trie = Trie()
        for w in words:
            trie.addWord(w)

        tn = len(target)

        best = [1000_000 for i in range(tn+1)]

        best[tn] = 0

        rangem = [[1000_000 for i in range(tn+1)] for j in range(15)]
        for i in range(15):
            rangem[i][tn] = 0

        twos = [1 for i in range(15)]
        for i in range(1,15):
            twos[i] = 2*twos[i-1]


        for i in range(tn-1, -1, -1): # max 5*1000
            tail = target[i:]
            clen = trie.prefixLen(tail)
            #print(f"i:{i}, clen:{clen}")

            if clen>0:
                tailmini = 1000_000
                for k in range(15):
                    l = twos[k]
                    #print(f"best:{best}")
                    #print(f"k:{k}, clen:{clen}, l:{l}, rangemk:{rangem[k]}")
                    if clen>=l:
                        tailmini = min(rangem[k][i+1], rangem[k][i+clen-l+1])
                        #print(f"celn>l: tailmini:{tailmini}")
                    else:
                        #print("break")
                        break
                
                best[i] = tailmini +1
            #print(f"i:{i}, best{best}")
            rangem[0][i] = best[i]
            for k in range(1,15):
                l = twos[k-1]
                if i + l <=tn:
                    rangem[k][i] = min(rangem[k-1][i], rangem[k-1][i+l])
                else:
                    break




            


        return best[0] if best[0]<1000_000 else -1



        
34639