# 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
*/
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://jaywin.gitbook.io/leetcode/solutions/0514-freedom-trail.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.