<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 Node:
    def __init__(self):
        self.children = [None] * 26
        self.id = -1 # root id

class Solution:
    # O(MN + M^3 + N^2)
    def minimumCost(self, source: str, target: str, original: List[str], changed: List[str], cost: List[int]) -> int:

        root = Node()

        self.count = 0

        # trie insert
        def insert(s):
            # O(N)
            # insert every char as a Node on the same path
            p = root
            # N
            for char in s:
                child_idx = ord(char) - ord('a')
                if not p.children[child_idx]:
                    p.children[child_idx] = Node()

                p = p.children[child_idx]
            # if leaf node does not have id, label it
            if p.id == -1:
                p.id = self.count
                self.count += 1
            return p.id
        
        M = len(original)
        dist = [[float('inf')] * (2*M) for _ in range(2*M)]

        # M * N
        for i in range(M):
            # insert into trie, get string's id
            # reverse: 方便之后倒着检查 for j in range(i, 0, -1)
            org = insert(original[i][::-1])
            cng = insert(changed[i][::-1])
            distance = cost[i]

            # initialize dist (min_path)
            dist[org][cng] = min(dist[org][cng], distance)
        
        # Floyd's
        # M^3
        for piv in range(self.count):
            for o in range(self.count):
                if dist[o][piv] == float('inf'): continue
                for c in range(self.count):
                    dist[o][c] = min(dist[o][c], dist[o][piv] + dist[piv][c])
        
        n = len(source)

        dp = [float('inf')] * (n + 1)
        dp[0] = 0

        # N^2
        for i in range(1,n+1):

            if source[i-1] == target[i-1]:
                dp[i] = dp[i-1]
            
            p = root
            q = root

            # scan prev string to see if they can be replaced
            for j in range(i, 0, -1):
                src = ord(source[j-1]) - ord('a')
                dest = ord(target[j-1]) - ord('a')
                p = p.children[src]
                q = q.children[dest]

                # the node dne, no letters come after 
                # (no valid string to be replaced with starting from i)
                if not p or not q: break
                # the node id == -1, its not the end of the valid string yet
                # keep looking
                if p.id == -1 or q.id == -1: continue

                dp[i] = min(dp[i], dist[p.id][q.id] + dp[j-1])
        
        return -1 if dp[-1] == float('inf') else dp[-1]


# class Solution:
#     def minimumCost(self, source: str, target: str, original: List[str], changed: List[str], cost: List[int]) -> int:

#         components = collections.defaultdict(set)

#         # group nodes by length
#         # M = len(original) = len(change)
#         # N = len(source)

#         # M
#         for i in range(len(original)):
#             length = len(original[i])
#             components[length].add(original[i])
#             components[length].add(changed[i])

#         # build graph (min_path)
#         # dist = {x: {y: cost}} 
#         dist = collections.defaultdict(lambda: collections.defaultdict(lambda: float('inf')))

#         # initialization
#         # M
#         for i in range(len(original)):
#             org = original[i]
#             cng = changed[i]
#             dist[org][cng] = min(dist[org][cng], cost[i])
#             dist[org][org] = 0
#             dist[cng][cng] = 0

#         # only update dist within the same component (the strings w same length)
#         # use Floyd's alg to find min dist between each substring

#         # M**3 ----> M**2
#         for length in components.keys():
#             # find the nodes within the same component
#             nodes = components[length]
#             for piv in nodes: # 转折点
#                 for org in nodes: # 起点
#                     if dist[org][piv] == float('inf'): continue
#                     for cng in nodes: # 终点
#                         dist[org][cng] = min(dist[org][cng], dist[org][piv] + dist[piv][cng])

#         n = len(source)

#         dp = [float('inf') for _ in range(n+1)]
#         dp[0] = 0
        
#         # N^3 total ---> N^2 * M
#         for i in range(1,n+1):
#             # 如果目前的char是相同的, 可以不用改
#             if target[i-1] == source[i-1]:
#                 # (继承前一位的答案)
#                 dp[i] = dp[i - 1]

#             for size, nodes in components.items():
#                 j = i-size
#                 if j < 0: continue
#                 src = source[(j):i]
#                 dest = target[(j):i]
#                 # N
#                 if src in nodes:
#                     dp[i] = min(dp[i], dp[(j)] + dist[src][dest])
#         return -1 if dp[n] == float('inf') else dp[n]
3918