<p>You are given two <strong>0-indexed</strong> strings <code>source</code> and <code>target</code>, both of length <code>n</code> and consisting of <strong>lowercase</strong> English characters. You are also given two <strong>0-indexed</strong> string arrays <code>original</code> and <code>changed</code>, and an integer array <code>cost</code>, where <code>cost[i]</code> represents the cost of converting the string <code>original[i]</code> to the string <code>changed[i]</code>.</p>

<p>You start with the string <code>source</code>. In one operation, you can pick a <strong>substring</strong> <code>x</code> from the string, and change it to <code>y</code> at a cost of <code>z</code> <strong>if</strong> there exists <strong>any</strong> index <code>j</code> such that <code>cost[j] == z</code>, <code>original[j] == x</code>, and <code>changed[j] == y</code>. You are allowed to do <strong>any</strong> number of operations, but any pair of operations must satisfy <strong>either</strong> of these two conditions:</p>

<ul>
	<li>The substrings picked in the operations are <code>source[a..b]</code> and <code>source[c..d]</code> with either <code>b &lt; c</code> <strong>or</strong> <code>d &lt; a</code>. In other words, the indices picked in both operations are <strong>disjoint</strong>.</li>
	<li>The substrings picked in the operations are <code>source[a..b]</code> and <code>source[c..d]</code> with <code>a == c</code> <strong>and</strong> <code>b == d</code>. In other words, the indices picked in both operations are <strong>identical</strong>.</li>
</ul>

<p>Return <em>the <strong>minimum</strong> cost to convert the string </em><code>source</code><em> to the string </em><code>target</code><em> using <strong>any</strong> number of operations</em>. <em>If it is impossible to convert</em> <code>source</code> <em>to</em> <code>target</code>,<em> return</em> <code>-1</code>.</p>

<p><strong>Note</strong> that there may exist indices <code>i</code>, <code>j</code> such that <code>original[j] == original[i]</code> and <code>changed[j] == changed[i]</code>.</p>

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

<pre>
<strong>Input:</strong> source = &quot;abcd&quot;, target = &quot;acbe&quot;, original = [&quot;a&quot;,&quot;b&quot;,&quot;c&quot;,&quot;c&quot;,&quot;e&quot;,&quot;d&quot;], changed = [&quot;b&quot;,&quot;c&quot;,&quot;b&quot;,&quot;e&quot;,&quot;b&quot;,&quot;e&quot;], cost = [2,5,5,1,2,20]
<strong>Output:</strong> 28
<strong>Explanation:</strong> To convert &quot;abcd&quot; to &quot;acbe&quot;, do the following operations:
- Change substring source[1..1] from &quot;b&quot; to &quot;c&quot; at a cost of 5.
- Change substring source[2..2] from &quot;c&quot; to &quot;e&quot; at a cost of 1.
- Change substring source[2..2] from &quot;e&quot; to &quot;b&quot; at a cost of 2.
- Change substring source[3..3] from &quot;d&quot; to &quot;e&quot; at a cost of 20.
The total cost incurred is 5 + 1 + 2 + 20 = 28. 
It can be shown that this is the minimum possible cost.
</pre>

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

<pre>
<strong>Input:</strong> source = &quot;abcdefgh&quot;, target = &quot;acdeeghh&quot;, original = [&quot;bcd&quot;,&quot;fgh&quot;,&quot;thh&quot;], changed = [&quot;cde&quot;,&quot;thh&quot;,&quot;ghh&quot;], cost = [1,3,5]
<strong>Output:</strong> 9
<strong>Explanation:</strong> To convert &quot;abcdefgh&quot; to &quot;acdeeghh&quot;, do the following operations:
- Change substring source[1..3] from &quot;bcd&quot; to &quot;cde&quot; at a cost of 1.
- Change substring source[5..7] from &quot;fgh&quot; to &quot;thh&quot; at a cost of 3. We can do this operation because indices [5,7] are disjoint with indices picked in the first operation.
- Change substring source[5..7] from &quot;thh&quot; to &quot;ghh&quot; at a cost of 5. We can do this operation because indices [5,7] are disjoint with indices picked in the first operation, and identical with indices picked in the second operation.
The total cost incurred is 1 + 3 + 5 = 9.
It can be shown that this is the minimum possible cost.
</pre>

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

<pre>
<strong>Input:</strong> source = &quot;abcdefgh&quot;, target = &quot;addddddd&quot;, original = [&quot;bcd&quot;,&quot;defgh&quot;], changed = [&quot;ddd&quot;,&quot;ddddd&quot;], cost = [100,1578]
<strong>Output:</strong> -1
<strong>Explanation:</strong> It is impossible to convert &quot;abcdefgh&quot; to &quot;addddddd&quot;.
If you select substring source[1..3] as the first operation to change &quot;abcdefgh&quot; to &quot;adddefgh&quot;, you cannot select substring source[3..7] as the second operation because it has a common index, 3, with the first operation.
If you select substring source[3..7] as the first operation to change &quot;abcdefgh&quot; to &quot;abcddddd&quot;, you cannot select substring source[1..3] as the second operation because it has a common index, 3, with the first operation.
</pre>

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

<ul>
	<li><code>1 &lt;= source.length == target.length &lt;= 1000</code></li>
	<li><code>source</code>, <code>target</code> consist only of lowercase English characters.</li>
	<li><code>1 &lt;= cost.length == original.length == changed.length &lt;= 100</code></li>
	<li><code>1 &lt;= original[i].length == changed[i].length &lt;= source.length</code></li>
	<li><code>original[i]</code>, <code>changed[i]</code> consist only of lowercase English characters.</li>
	<li><code>original[i] != changed[i]</code></li>
	<li><code>1 &lt;= cost[i] &lt;= 10<sup>6</sup></code></li>
</ul>

class TrieNode:
    def __init__(self,data):
        self.children={}
        self.data=data
        self.isWord=False
    def set_word(self,dest,cost):
        self.isWord=True


class Solution:
    def FW(self,original: List[str], changed: List[str], cost: List[int]):
        S=set()
        for i in range(len(original)):
            S.add(original[i])
            S.add(changed[i])
        for it in S:
            self.index[it]=len(self.index)
        
        # Cost matrix
        N=len(self.index)
        for i in range(N):
            for j in range(N):
                self.distances[i][j]=float('inf') if i!=j else 0
        for i in range(len(original)):
            o_i,o_c=self.index[original[i]],self.index[changed[i]]
            self.distances[o_i][o_c]=min(self.distances[o_i][o_c], cost[i])

        for k in range(N):
            for i in range(N):
                if self.distances[i][k] != float('inf'):
                    for j in range(N):
                        if self.distances[k][j]!=float('inf'):
                            self.distances[i][j]=min(self.distances[i][j],
                                self.distances[i][k]+self.distances[k][j])

        
    def minimumCost(self, source: str, target: str, original: List[str], changed: List[str], cost: List[int]) -> int:
        self.distances=[[float('inf')]*1000 for _ in range(1000)]
        self.index={}
        self.INF=10**20

        root=TrieNode('\0')

        # Build Trie
        def insert_trie(root,source,dest,cost,i):
            if i==len(source):
                root.set_word(dest,cost)
                return 
            if source[i] not in root.children:
                node=TrieNode(source[i])
                root.children[source[i]]=node 
                insert_trie(node, source, dest, cost, i+1)
            else:
                insert_trie(root.children[source[i]], source, dest, cost, i+1)
        for i in range(len(original)):
            insert_trie(root, original[i], changed[i], cost[i],0)

        # Floyd Warshall 
        self.FW(original,changed,cost)

        @lru_cache(maxsize=None)  # Use memoization for efficiency
        def helper(i):
            if i==len(target):
                return 0
            # if self.dp[i]==-1:
            c1,c2=self.INF,self.INF 
            # match
            if source[i]==target[i]:
                c1=helper(i+1)
            node=root
            source_substr, target_substr = [], []
            # substr
            for j in range(i,len(source)):
                if source[j] not in node.children:
                    break
                source_substr.append(source[j])
                target_substr.append(target[j])
                node=node.children[source[j]]
                if node.isWord:
                    jt = self.index.get("".join(source_substr), -1)
                    kt = self.index.get("".join(target_substr), -1)
                    if jt != -1 and kt !=-1 and self.distances[jt][kt] !=float('inf'):
                        c2=min(c2,helper(j+1)+self.distances[jt][kt])
            return min(c1,c2)

        ans=helper(0)
        return ans if ans !=self.INF else -1
6366