<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 n;
    vector<vector<int>> minSteps;
    vector<vector<int>> cache;
    unordered_map<char, vector<int>> potential_idxs;
    int findRotateSteps(string ring, string key) {
        // we only have two decisions: clockwise or anti-clockwise
        // in the string, this is really left or right from curr position, with a looparound


        // build a table of distances of char to another char for easy reference
        // remember all distances have +1 to press the button
        // minSteps[from][to] contains num steps incurred to transition
        n = ring.length();
        minSteps.resize(n, vector<int>(n, 1));
        for (int i=0; i<n; i++) {
            for (int j=i; j<n; j++) {
                minSteps[i][j] = 1 + min(i + n - j, j - i); // CW or anti-CW
                minSteps[j][i] = minSteps[i][j];
            }
        }

        for (int i=0; i<n; i++) {
            potential_idxs[ring[i]].push_back(i);
        }

        cache.resize(key.size(), vector<int>(n,-1));
        int min_steps_to_finish = INT_MAX;
        // find starting cost for initial turn
        for (int j : potential_idxs[key[0]]) {
            int starting_cost = minSteps[0][j] + dfs(j, 0, key);
            min_steps_to_finish = min(min_steps_to_finish, starting_cost);
        }
        return min_steps_to_finish;

    }

    int dfs(int i, int idx, string key) {
        // from idx to idx + 1
        // base case, button press accounted for in transition to this state 
        if (idx == key.size() - 1) return 0;
        if (cache[idx][i] != -1) return cache[idx][i];
        // check best of CW or anti-CW
        int min_steps_to_finish = INT_MAX;
        char next_char = key[idx+1];
        for (int j : potential_idxs[next_char]) {
            int steps_to_finish = minSteps[i][j] + dfs(j, idx+1, key);
            min_steps_to_finish = min(min_steps_to_finish, steps_to_finish);
        }

        cache[idx][i] = min_steps_to_finish;
        return min_steps_to_finish;
    }
};
51953