<p>You are given a string <code>target</code>, an array of strings <code>words</code>, and an integer array <code>costs</code>, both arrays of the same length.</p>

<p>Imagine an empty string <code>s</code>.</p>

<p>You can perform the following operation any number of times (including <strong>zero</strong>):</p>

<ul>
	<li>Choose an index <code>i</code> in the range <code>[0, words.length - 1]</code>.</li>
	<li>Append <code>words[i]</code> to <code>s</code>.</li>
	<li>The cost of operation is <code>costs[i]</code>.</li>
</ul>

<p>Return the <strong>minimum</strong> cost to make <code>s</code> equal to <code>target</code>. If it&#39;s not possible, 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">target = &quot;abcdef&quot;, words = [&quot;abdef&quot;,&quot;abc&quot;,&quot;d&quot;,&quot;def&quot;,&quot;ef&quot;], costs = [100,1,1,10,5]</span></p>

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

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

<p>The minimum cost can be achieved by performing the following operations:</p>

<ul>
	<li>Select index 1 and append <code>&quot;abc&quot;</code> to <code>s</code> at a cost of 1, resulting in <code>s = &quot;abc&quot;</code>.</li>
	<li>Select index 2 and append <code>&quot;d&quot;</code> to <code>s</code> at a cost of 1, resulting in <code>s = &quot;abcd&quot;</code>.</li>
	<li>Select index 4 and append <code>&quot;ef&quot;</code> to <code>s</code> at a cost of 5, resulting in <code>s = &quot;abcdef&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">target = &quot;aaaa&quot;, words = [&quot;z&quot;,&quot;zz&quot;,&quot;zzz&quot;], costs = [1,10,100]</span></p>

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

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

<p>It is impossible to make <code>s</code> equal to <code>target</code>, so we return -1.</p>
</div>

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

<ul>
	<li><code>1 &lt;= target.length &lt;= 5 * 10<sup>4</sup></code></li>
	<li><code>1 &lt;= words.length == costs.length &lt;= 5 * 10<sup>4</sup></code></li>
	<li><code>1 &lt;= words[i].length &lt;= target.length</code></li>
	<li>The total sum of <code>words[i].length</code> is less than or equal to <code>5 * 10<sup>4</sup></code>.</li>
	<li><code>target</code> and <code>words[i]</code> consist only of lowercase English letters.</li>
	<li><code>1 &lt;= costs[i] &lt;= 10<sup>4</sup></code></li>
</ul>

def get_common_prefix(s1, s2):
    length = 0
    for i in range(min(len(s1), len(s2))):
        if s1[i] == s2[i]:
            length += 1
        else:
            break
    return s1[:length]

class Trie:
    def __init__(self):
        self.children = defaultdict(Trie)
        self.cost = float("infinity")
        self.starts = {}

    def build(self, words, costs):
        pairs = []
        for cost_index, word in enumerate(words):
            pairs.append((word, costs[cost_index]))
        pairs.sort()
        for word, cost in pairs:
            self.insert(word, cost)

    def insert(self, word, cost):
        trie = self
        to_insert = word
        while to_insert:
            before_scan = to_insert
            for s, child in trie.children.items():
                prefix = get_common_prefix(to_insert, s)
                if not prefix:
                    continue
                if prefix == s:
                    to_insert = to_insert[len(prefix):]
                    trie = trie.children[s]
                    break

                suffix = s[len(prefix):]
                grandchild = Trie()
                grandchild.cost = child.cost
                grandchild.children = child.children

                del trie.children[s]
                new_child = Trie()                
                trie.children[prefix] = new_child
                new_child.children = defaultdict(Trie)
                new_child.children[suffix] = grandchild

                trie = new_child
                to_insert = to_insert[len(prefix):]
                break
            if before_scan == to_insert:
                trie = trie.children[to_insert]
                to_insert = ""

        trie.cost = min(trie.cost, cost)

    def build_starts(self):
        for s, child in self.children.items():
            self.starts[s[0]] = s
            child.build_starts()

class Solution:
    def minimumCost(self, target: str, words: List[str], costs: List[int]) -> int:
        compressed_costs = Trie()
        compressed_costs.build(words, costs)
        compressed_costs.build_starts()

        @cache
        def fn(i):
            if i >= len(target):
                return 0
            best = float("infinity")
            trie = compressed_costs
            j = i
            while j < len(target):
                prefix = trie.starts.get(target[j])
                if not prefix or prefix != target[j:j+len(prefix)]:
                    return best

                j += len(prefix)
                trie = trie.children[prefix]
                if trie.cost < best:
                    best = min(best, trie.cost + fn(j))
            return best

        answer = fn(0)
        return answer if answer != float("infinity") else -1

107100