> For the complete documentation index, see [llms.txt](https://jaywin.gitbook.io/leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://jaywin.gitbook.io/leetcode/solutions/0514-freedom-trail.md).

# 0514. Freedom Trail

<https://leetcode.com/problems/freedom-trail>

## Description

In the video game Fallout 4, the quest **"Road to Freedom"** requires players to reach a metal dial called the **"Freedom Trail Ring"** and use the dial to spell a specific keyword to open the door.

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

Initially, the first character of the ring is aligned at the `"12:00"` direction. You should spell all the characters in `key` one by one by rotating `ring` clockwise or anticlockwise to make each character of the string key aligned at the `"12:00"` direction and then by pressing the center button.

At the stage of rotating the ring to spell the key character `key[i]`:

1. You can rotate the ring clockwise or anticlockwise by one place, which counts as **one step**. The final purpose of the rotation is to align one of `ring`'s characters at the `"12:00"` direction, where this character must equal `key[i]`.
2. If the character `key[i]` has been aligned at the `"12:00"` direction, press the center button to spell, which also counts as **one step**. After the pressing, you could begin to spell the next character in the key (next stage). Otherwise, you have finished all the spelling.

**Example 1:**

![](https://assets.leetcode.com/uploads/2018/10/22/ring.jpg)

```
**Input:** ring = "godding", key = "gd"
**Output:** 4
**Explanation:**
For the first key character 'g', since it is already in place, we just need 1 step to spell this character. 
For the second key character 'd', we need to rotate the ring "godding" anticlockwise by two steps to make it become "ddinggo".
Also, we need 1 more step for spelling.
So the final output is 4.
```

**Example 2:**

```
**Input:** ring = "godding", key = "godding"
**Output:** 13
```

**Constraints:**

* `1 <= ring.length, key.length <= 100`
* `ring` and `key` consist of only lower case English letters.
* It is guaranteed that `key` could always be spelled by rotating `ring`.

## ac

```java
class Solution {
    public int findRotateSteps(String ring, String key) {
        int rn = ring.length(), kn = key.length();
        int[][] memo = new int[rn][kn];
        dfs(ring, 0, key, 0, memo);
        return memo[0][0];
    }

    private int dfs(String ring, int ri, String key, int ki, int[][] memo) {
        // exit, key hit the end
        if (ki >= key.length()) return 0;
        if (memo[ri][ki] != 0) return memo[ri][ki];

        // clock wise
        int cnt1 = 1, r1 = ri;
        while (ring.charAt(r1) != key.charAt(ki)) {
            r1 = (r1 + 1) % ring.length();
            cnt1++;
        }
        cnt1 += dfs(ring, r1, key, ki+1, memo); // find next

        // anti-clockwise
        int cnt2 = 1, r2 = ri;
        while (ring.charAt(r2) != key.charAt(ki)) {
            r2 = (r2 - 1 + ring.length()) % ring.length();
            cnt2++;
        }
        cnt2 += dfs(ring, r2, key, ki+1, memo);// find next

        // return smaller one
        memo[ri][ki] = Math.min(cnt1, cnt2);
        return memo[ri][ki];
    }
}

/*
DFS, divide & conquer. 1) how many steps clockwise?  2) hwo many of anti-clockwise? 3) both plus next iterate result, get the min. 4) use int[ring.length()][key.length()] memo to avoid duplicate calculation
*/
```