<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 Solution:
    def minimumCost(self, source: str, target: str, original: List[str], changed: List[str], cost: List[int]) -> int:
        class TrieNode:
            def __init__(self):
                self.is_word = False 
                # indicates that at the character which points to this node - the word terminates, when it is False - self.vertex_id is set to -1
                self.vertex_id = -1 # represents the vertex_id of the string in original / changed
                self.children = {} # map of character to the corresponding trie node

        def add_word(root, original_str, vertex_id):
            temp = root
            for char in original_str:
                if char not in temp.children:
                    temp.children[char] = TrieNode()
                temp = temp.children[char]
            # in the end temp points to the node which is represented by the last char of the string
            temp.vertex_id = vertex_id


        # Programming Trick 1: you need a unique index for each string to run the floydd warshall for all the substrings - you could do it with a dictionary of dictionaries though
        # represents all possible string changes in a graph in adjacency list format
        string_to_vertex_id = {}
        n = 0 # represents curr_avail_id
        root = TrieNode()
        for el in original:
            if el not in string_to_vertex_id:
                string_to_vertex_id[el] = n
                add_word(root, el, n)
                n += 1
                

        for el in changed:
            if el not in string_to_vertex_id:
                string_to_vertex_id[el] = n
                add_word(root, el, n)
                n += 1
        graph = [[float('inf')] * n for _ in range(n)] # n is 1 more than last id but represents size correctly

        # map of length to all original strings that are possible from that
        same_len_originals = defaultdict(set)
        same_len_changed = defaultdict(set)
        for i, (o, c) in enumerate(zip(original, changed)):
            row, col = string_to_vertex_id[o], string_to_vertex_id[c]
            graph[row][col] = min(graph[row][col], cost[i])
            same_len_originals[len(o)].add(o)
            same_len_changed[len(c)].add(c) # len(o) == len(c)
        
        # Improvement 1: Do floydd warshall only for the strings of same size
        # Insight: there are only one way edges - from original to changed
        for string_len in same_len_originals.keys():
            # get all original strings of the same length
            # Note that i has to be original, j has to be changed and k must 
            # be something common so can be picked from either
            for el in same_len_originals[string_len]:
                for original_str in same_len_originals[string_len]:
                    for changed_str in same_len_changed[string_len]:
                        k, i, j = string_to_vertex_id[el], string_to_vertex_id[original_str], string_to_vertex_id[changed_str]
                        graph[i][j]=min(graph[i][j], graph[i][k] + graph[k][j])
          
        # Now do a dfs on the source and the target string conversion with dp
        n = len(source)
        # dp[i] means changing first i letters of the source to target; 
        # actual conversion will start from dp[1] and ans is dp[n]
        dp = [float('inf')] * (n +1)
        dp[0] = 0
        
        changed = set(changed)
        # in each iteration we populate the cells in dp ahead of the current index
        for i in range(n):
            # we start `after` the end of the previous iteration 
            # i.e. populate next one to where dp[i] != inf
            if dp[i] == float('inf'):
                continue
            if source[i] == target[i]:
                # dp[i+1] may already be populated as the end of some other string transformation
                dp[i+1] = min(dp[i+1], dp[i])
                # since source == target in this, therefore we shouldn't do any transformations
                # this is assuming that tranformations like ab -> ad are not valid ones

            # generate all sub-strings which are starting from source[i] till end (source[-1])
            # sub-string should be of the same size as one of the originals
            temp_original = temp_changed = root
            for j in range(i, len(source)):
                # Now for each dp[j], you have to try strings of all unique lengths in original
                if source[j] not in temp_original.children or target[j] not in temp_changed.children:
                    break
                temp_original, temp_changed = temp_original.children[source[j]], temp_changed.children[target[j]]

                if temp_original.vertex_id != -1 and temp_changed.vertex_id != -1:
                    s,v = temp_original.vertex_id, temp_changed.vertex_id
                    dp[j+1] = min(dp[j+1], dp[i] + graph[s][v])
                # # we try these by iterating the length (governed by j) from i to end
                # # and then checking all original strings of that same size
                # for el in same_len_originals.get(j-i+1, []):
                #     source_substring, target_substring = source[i:j+1], target[i:j+1]
                #     # if the original is same as source + there is a path from source to target substring
                #     # then this means that it is a valid transformation
                #     if source_substring == el and target_substring in changed:
                #         s, v = string_to_vertex_id[source_substring], string_to_vertex_id[target_substring]
                #         dp[j+1] = min(dp[j+1], dp[i] + graph[s][v])
        return -1 if dp[n] == float('inf') else dp[n]

4099