<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:
    def findRotateSteps(self, ring: str, key: str) -> int:
        return self.fun2(ring, key)

    def fun3(self, ring: str, key: str) -> int:
        dct = collections.defaultdict(list)
        for i, c in enumerate(ring):
            dct[c].append(i)
        n = len(ring)

        # dp[i][j] 表示ring第j个字符为12点方向时，前i个key字符的最小步数
        dp = [[0] * n for _ in range(len(key) + 1)]

        for i in range(len(key)):
            for j in range(n):
                res = float("inf")
                for k in dct[key[i]]:
                    ans = dp[i][k] + min(abs(k - j), n - abs(k - j)) + 1
                    res = min(res, ans)
                dp[i + 1][j] = res

        return min(dp[-1])

    def fun2(self, ring: str, key: str) -> int:
        dct = collections.defaultdict(list)
        for i, c in enumerate(ring):
            dct[c].append(i)
        n = len(ring)
        m = len(key)
        dp = [[-1] * (m + 1) for _ in range(n)]

        def dfs(i, j):
            if dp[i][j] != -1:
                return dp[i][j]

            if j >= m:
                dp[i][j] = 0
                return dp[i][j]

            c = key[j]

            if c == ring[i]:
                dp[i][j] = 1 + dfs(i, j + 1)
                return dp[i][j]

            if len(dct[c]) == 1:
                k1 = dct[c][0]
                dp[i][j] = min(abs(k1 - i), n - abs(k1 - i)) + 1 + dfs(k1, j + 1)
                return dp[i][j]

            k = bisect.bisect_left(dct[c], i)
            if k == len(dct[c]) or k == 0:
                k1 = dct[c][-1]
                k2 = dct[c][0]
            else:
                k1 = dct[c][k - 1]
                k2 = dct[c][k]

            r1 = min(abs(k1 - i), n - abs(k1 - i)) + 1 + dfs(k1, j + 1)
            r2 = min(abs(k2 - i), n - abs(k2 - i)) + 1 + dfs(k2, j + 1)

            dp[i][j] = min(r1, r2)
            return dp[i][j]

        res = dfs(0, 0)
        return res

    def fun1(self, ring: str, key: str) -> int:
        dct = collections.defaultdict(list)
        for i, c in enumerate(ring):
            dct[c].append(i)
        n = len(ring)

        @functools.lru_cache()
        def dfs(i, str1):
            if not str1:
                return 0

            c = str1[0]

            if c == ring[i]:
                return 1 + dfs(i, str1[1:])

            if len(dct[c]) == 1:
                k1 = dct[c][0]
                return min(abs(k1 - i), n - abs(k1 - i)) + 1 + dfs(k1, str1[1:])

            j = bisect.bisect_left(dct[c], i)
            if j == len(dct[c]) or j == 0:
                k1 = dct[c][-1]
                k2 = dct[c][0]
            else:
                k1 = dct[c][j - 1]
                k2 = dct[c][j]

            r1 = min(abs(k1 - i), n - abs(k1 - i)) + 1 + dfs(k1, str1[1:])
            r2 = min(abs(k2 - i), n - abs(k2 - i)) + 1 + dfs(k2, str1[1:])

            return min(r1, r2)

        return dfs(0, key)


18000