<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 letters. You are also given two <strong>0-indexed</strong> character arrays <code>original</code> and <code>changed</code>, and an integer array <code>cost</code>, where <code>cost[i]</code> represents the cost of changing the character <code>original[i]</code> to the character <code>changed[i]</code>.</p>

<p>You start with the string <code>source</code>. In one operation, you can pick a character <code>x</code> from the string and change it to the character <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>.</p>

<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. 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 the string &quot;abcd&quot; to string &quot;acbe&quot;:
- Change value at index 1 from &#39;b&#39; to &#39;c&#39; at a cost of 5.
- Change value at index 2 from &#39;c&#39; to &#39;e&#39; at a cost of 1.
- Change value at index 2 from &#39;e&#39; to &#39;b&#39; at a cost of 2.
- Change value at index 3 from &#39;d&#39; to &#39;e&#39; 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;aaaa&quot;, target = &quot;bbbb&quot;, original = [&quot;a&quot;,&quot;c&quot;], changed = [&quot;c&quot;,&quot;b&quot;], cost = [1,2]
<strong>Output:</strong> 12
<strong>Explanation:</strong> To change the character &#39;a&#39; to &#39;b&#39; change the character &#39;a&#39; to &#39;c&#39; at a cost of 1, followed by changing the character &#39;c&#39; to &#39;b&#39; at a cost of 2, for a total cost of 1 + 2 = 3. To change all occurrences of &#39;a&#39; to &#39;b&#39;, a total cost of 3 * 4 = 12 is incurred.
</pre>

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

<pre>
<strong>Input:</strong> source = &quot;abcd&quot;, target = &quot;abce&quot;, original = [&quot;a&quot;], changed = [&quot;e&quot;], cost = [10000]
<strong>Output:</strong> -1
<strong>Explanation:</strong> It is impossible to convert source to target because the value at index 3 cannot be changed from &#39;d&#39; to &#39;e&#39;.
</pre>

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

<ul>
	<li><code>1 &lt;= source.length == target.length &lt;= 10<sup>5</sup></code></li>
	<li><code>source</code>, <code>target</code> consist of lowercase English letters.</li>
	<li><code>1 &lt;= cost.length == original.length == changed.length &lt;= 2000</code></li>
	<li><code>original[i]</code>, <code>changed[i]</code> are lowercase English letters.</li>
	<li><code>1 &lt;= cost[i] &lt;= 10<sup>6</sup></code></li>
	<li><code>original[i] != changed[i]</code></li>
</ul>

# iterate over both source and target arrays and compare the values at same index. If they are different, need to run a dfs on every possibility of how you can convert a letter using the original/changed/cost arrays
# Seems like you can use dynamic programming to memoize the conversions. If you store {(curLetter, convertedLetter): cost} in memo array, then when you reach a combination of having a given letter and needing to convert to the target letter, you can just search memo array and return that, you know that it can be converted to the convertedLetter
# optimization problem, so that suggests dynamic programming or greedy usually.
# 
"""
class Solution:
    def __init__(self):
        self.memo = {} # {(curLetter, convertedLetter): cost}
        self.source = ""
        self.target = ""
        self.original = []
        self.changed = []
        self.cost = []

    def minimumCost(self, source: str, target: str, original: List[str], changed: List[str], cost: List[int]) -> int:
        self.source = source
        self.target = target
        self.original = original
        self.changed = changed
        self.cost = cost

        res = 0
        for i in range(len(self.source)):
            res += self.dfs(i, i)
        
        return res

    def dfs(self, srcIdx, tgtIdx):
        if srcIndex >= len(self.source) or tgtIdx >= len(self.target):
            return
        
        if (self.source[srcIdx], self.target[tgtIdx]) in self.memo:
            return self.memo[self.source[srcIdx], self.target[tgtIdx]]

        
        

        return min()
"""   

# approach 2
    # Dijkstras approach. Here you are looking at the minimum cost to reach a destination, and since we are doing something similar to a dfs to search through the possibilities, we want to follow the shortest path to reach the target cost. So usually you would have a list of [fromNode, toNode, weight], here you have a source letter, a target letter, and the weights are stored in the cost array. 

    # adjacency list
        # not bidirectional so you don't to append the inverse way
        # structure of adjacency list is {origChar: (convertedChar, cost)}, since you can have c be converted to multiple letters involving different costs for each

    # minHeap, need it structured to be (cost, curLetter) where curLetter will progress down to the target letter, and cost is the current cost of the path
        # want different minheap for each recursive call since you are calculating each path separately.
        # minheap assures that you are travelling down the lowest cost route

    # within dijkstras you need a minCostMap that stores {letter: cost} and you want to update that if your current letter has a lower cost than a previous path found you want to overwrite that.
        # We are also using a memoization array that stores (startLetter, targetLetter) as the key so that if you start dijkstras and need to repeat the work to convert one character to another then you can just pull from memoization
        # The reason why the visited set works is because 

    # dijkstras base cases
        # if your current letter through the dfs exploring the adjacency list has reached the destination letter then you can return that current cost since you used the minheap to explore the shortest path and you will have that lowest cost
        # if the current letter is in the visited set, you want to skip over it since you already explored that path completely. Due to the nature of the minheap, if you reach a character you already explored, since minheap chooses the shortest path, then there is no point in revisiting this letter since it has already been a part of the shortest path
        # if a node is revisited later it means that you are just visiting that node but with a longer path so there is no reason to revisit it.

    # memoization
        # adds a small performance improvement since it only works for the starting letter since you can only check memo array if you fully computed all paths for the letter, so you can't use curletter since you could be reprocessing things you already fully processed and run into time limit exceeded

class Solution:
    def __init__(self):
        self.memo = {} # {(curLetter, convertedLetter): cost}

    def minimumCost(self, source: str, target: str, original: List[str], changed: List[str], cost: List[int]) -> int:
        self.adjList = {} # {origChar: (convertedChar, cost)}
        res = 0

        # build adjacency list
        for i in range(len(original)):
            if original[i] not in self.adjList:
                self.adjList[original[i]] = []
            self.adjList[original[i]].append((changed[i], cost[i]))
        
        # iterate over each character in adjList and accrue cost
        for startLetter, targetLetter in zip(source, target):
            curCost = self.dijkstras(startLetter, targetLetter)
            if curCost == -1:
                return -1
            res += curCost
        
        return res

    def dijkstras(self, startLetter, targetLetter):
        if (startLetter, targetLetter) in self.memo:
            return self.memo[(startLetter, targetLetter)]

        minHeap = [(0, startLetter)] # (curCost, curLetter)
        visitedSet = set()

        while minHeap:
            curCost, curLetter = heappop(minHeap)

            if (startLetter, targetLetter) in self.memo:
                return self.memo[(startLetter, targetLetter)]
                
            if curLetter == targetLetter:
                self.memo[(startLetter, targetLetter)] = curCost
                return curCost
            
            if curLetter in visitedSet:
                continue
            visitedSet.add(curLetter)

            # explore adjacent letters. Note you can reach a letter that you didn't populate in original adjacency list. Need handling
            if curLetter in self.adjList:
                for adjLetter, adjCost in self.adjList[curLetter]:
                    if adjLetter not in visitedSet:
                        heappush(minHeap, (curCost + adjCost, adjLetter))

        return -1


2883