<p>In the video game Fallout 4, the quest <strong>&quot;Road to Freedom&quot;</strong> requires players to reach a metal dial called the <strong>&quot;Freedom Trail Ring&quot;</strong> and use the dial to spell a specific keyword to open the door.</p>

<p>Given a string <code>ring</code> that represents the code engraved on the outer ring and another string <code>key</code> that represents the keyword that needs to be spelled, return <em>the minimum number of steps to spell all the characters in the keyword</em>.</p>

<p>Initially, the first character of the ring is aligned at the <code>&quot;12:00&quot;</code> direction. You should spell all the characters in <code>key</code> one by one by rotating <code>ring</code> clockwise or anticlockwise to make each character of the string key aligned at the <code>&quot;12:00&quot;</code> direction and then by pressing the center button.</p>

<p>At the stage of rotating the ring to spell the key character <code>key[i]</code>:</p>

<ol>
	<li>You can rotate the ring clockwise or anticlockwise by one place, which counts as <strong>one step</strong>. The final purpose of the rotation is to align one of <code>ring</code>&#39;s characters at the <code>&quot;12:00&quot;</code> direction, where this character must equal <code>key[i]</code>.</li>
	<li>If the character <code>key[i]</code> has been aligned at the <code>&quot;12:00&quot;</code> direction, press the center button to spell, which also counts as <strong>one step</strong>. After the pressing, you could begin to spell the next character in the key (next stage). Otherwise, you have finished all the spelling.</li>
</ol>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img src="https://assets.leetcode.com/uploads/2018/10/22/ring.jpg" style="width: 450px; height: 450px;" />
<pre>
<strong>Input:</strong> ring = &quot;godding&quot;, key = &quot;gd&quot;
<strong>Output:</strong> 4
<strong>Explanation:</strong>
For the first key character &#39;g&#39;, since it is already in place, we just need 1 step to spell this character. 
For the second key character &#39;d&#39;, we need to rotate the ring &quot;godding&quot; anticlockwise by two steps to make it become &quot;ddinggo&quot;.
Also, we need 1 more step for spelling.
So the final output is 4.
</pre>

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

<pre>
<strong>Input:</strong> ring = &quot;godding&quot;, key = &quot;godding&quot;
<strong>Output:</strong> 13
</pre>

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

<ul>
	<li><code>1 &lt;= ring.length, key.length &lt;= 100</code></li>
	<li><code>ring</code> and <code>key</code> consist of only lower case English letters.</li>
	<li>It is guaranteed that <code>key</code> could always be spelled by rotating <code>ring</code>.</li>
</ul>

class Solution {
public:
    int findDistance(int n, int start, int target){
        int forward = abs(start - target);
        int backward = n - forward;

        return min(forward, backward);
    }

    int modifiedDijkstra(string& ring, string& key, unordered_map<char, vector<int>>& adj){
        int ring_len = ring.length();
        int key_len = key.length();

        priority_queue<vector<int>, vector<vector<int>>, greater<vector<int>>> pq; // inner vector -> (cost, ring_index, key_index)
        // set<pair<int, int>> visited;
        vector<vector<bool>> visited(ring_len+1, vector<bool>(key_len, false));
        pq.push({0, 0, 0});

        while(!pq.empty()){
            auto item = pq.top();
            int d = item[0];
            int ri = item[1];
            int ki = item[2];
            pq.pop();

            if(ki >= key_len) {
                return d;
            }

            if(visited[ri][ki]) continue;
            visited[ri][ki] = true;
            // if(visited.find({ri,ki}) != visited.end()) {
            //     continue;
            // }
            // visited.insert({ri, ki});

            int ch = key[ki];

            for(auto& v: adj[ch]){
                int cost = findDistance(ring_len, ri, v);
                int total_cost = d + cost;

                pq.push({total_cost, v, ki + 1});
            }
        }

        return 0;
    }
    int func(string& ring, string& key, unordered_map<char, vector<int>>& adj){
        int n = ring.length();
        int m = key.length();
        priority_queue<vector<int>, vector<vector<int>>, greater<vector<int>>> pq;
        pq.push({0, 0, 0});

        set<pair<int, int>> visited;
        
        int totalSteps = 0;
        while (!pq.empty()) {
            vector<int> vec = pq.top();
            pq.pop();
            
            totalSteps    = vec[0];
            int ringIndex = vec[1];
            int keyIndex  = vec[2];
            
            if (keyIndex == m) {
                break;
            }
            
            if (visited.count({ringIndex, keyIndex})) {
                continue;
            }

            visited.insert({ringIndex, keyIndex});
            
            for (int nextIndex : adj[key[keyIndex]]) {
                pq.push({totalSteps + findDistance(n, ringIndex, nextIndex), 
                            nextIndex, keyIndex + 1});
            }
        }
        
        return totalSteps;
    }
    int findRotateSteps(string ring, string key) {
        unordered_map<char, vector<int>> adj;
        for(int i=0; i<ring.length(); i++){
            int ch = ring[i];
            adj[ch].push_back(i);
        }
        int stepsForRotating = modifiedDijkstra(ring, key, adj);
        int stepsForPressing = key.size();

        return stepsForRotating + stepsForPressing;
    }
};
29768