# 514     Freedom Trail

## 514. [Freedom Trail](https://leetcode.com/problems/freedom-trail/description/)

## 1. Question

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 in order to open the door.

Given a string **ring**, which represents the code engraved on the outer ring and another string **key**, which represents the keyword

needs to be spelled. You need to find the **minimum** number of steps in order to spell all the characters in the keyword.

Initially, the first character of the **ring** is aligned at 12:00 direction. You need to spell all the characters in the string **key**

one by one by rotating the ring clockwise or anticlockwise to make each character of the string **key** aligned at 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 **one place**, which counts as 1 step. The final purpose of the rotation is to align one of the string **ring's** characters at the 12:00 direction, where this character must equal to the character **key\[i]**.
2. If the character **key\[i]** has been aligned at the 12:00 direction, you need to press the center button to spell, which also counts as 1 step. After the pressing, you could begin to spell the next character in the key (next stage), otherwise, you've finished all the spelling.

**Example:**

![](https://2090187494-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LyrKyMPRGqB46Bg_cJ1%2F-LyrL-KnnBaE1T0K6SeT%2F-LyrLRjwdu8w03c07Nj5%2Ffreedom_trail_ex1.png?generation=1579329126622630\&alt=media)

```
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.
```

**Note:**

1. Length of both ring and **key** will be in range 1 to 100.
2. There are only lowercase letters in both strings and might be some duplcate characters in both strings.
3. It's guaranteed that string **key** could always be spelled by rotating the string **ring**.

## 2. Implementation

**(1) DFS (TLE)**

```java
class Solution {
    public int findRotateSteps(String ring, String key) {
        if (ring == null || ring.length() == 0 || key == null || key.length() == 0) {
            return 0;
        }

        int m = ring.length();
        int n = key.length();

        Map<Character, Set<Integer>> map = new HashMap();

        for (int i = 0; i < m; i++) {
            map.putIfAbsent(ring.charAt(i), new HashSet());
            map.get(ring.charAt(i)).add(i);
        }

        int len = ring.length();
        int steps = findMinRotateSteps(0, 0, key, len, map);
        return steps == Integer.MAX_VALUE ? -1 : steps;
    }

    public int findMinRotateSteps(int ringIndex, int keyIndex, String key, int len, Map<Character, Set<Integer>> map) {
        if (keyIndex == key.length()) {
            return 0;
        }

        int minSteps = Integer.MAX_VALUE;

        for (int nextRingIndex : map.get(key.charAt(keyIndex))) {
            int distance = Math.min(Math.abs(ringIndex - nextRingIndex), len - Math.abs(ringIndex - nextRingIndex));
            int steps = findMinRotateSteps(nextRingIndex, keyIndex + 1, key, len, map);
            minSteps = Math.min(minSteps, distance + steps + 1);
        }
        return minSteps;
    }
}
```

**(2) DFS + Memoization**

```java
class Solution {
    public int findRotateSteps(String ring, String key) {
        if (ring == null || ring.length() == 0 || key == null || key.length() == 0) {
            return 0;
        }

        int m = ring.length();
        int n = key.length();

        // cache[i][j] store the min steps to reach key[j] from ring[i]
        int[][] cache = new int[m][n];
        for (int i = 0; i < m; i++) {
            Arrays.fill(cache[i], Integer.MAX_VALUE);
        }

        // map store the index of character in ring
        Map<Character, Set<Integer>> map = new HashMap();

        for (int i = 0; i < ring.length(); i++) {
            map.putIfAbsent(ring.charAt(i), new HashSet());
            map.get(ring.charAt(i)).add(i);
        }

        int len = ring.length();
        int steps = findMinRotateSteps(0, 0, key, map, len, cache);
        return steps == Integer.MAX_VALUE ? -1 : steps;
    }

    public int findMinRotateSteps(int ringIndex, int keyIndex, String key, Map<Character, Set<Integer>> map, int len, int[][] cache) {
        if (keyIndex == key.length()) {
            return 0;
        }

        if (cache[ringIndex][keyIndex] != Integer.MAX_VALUE) {
            return cache[ringIndex][keyIndex];
        }

        int minSteps = Integer.MAX_VALUE;
        int steps = 0;    

        // For each character in the key, check their index in the ring
        for (int nextRingIndex : map.get(key.charAt(keyIndex))) {
            // The min step to reach key.charAt(keyIndex) from ring.charAt(ringIndex) consists of three parts:
            // (1) Steps to reach from current ring character to the next one: there are two ways to get the next ring         index:clockwise rotate the ring to the next character or anti-clockwise ratotate the ring
            // (2) the minimum steps to reach key.charAt(keyIndex + 1) from ring.charAt(nextRingIndex), this can be achieved by calling dfs() recursively
            // (3) 1 step for the spell
            int distance = Math.min(Math.abs(ringIndex - nextRingIndex), len - Math.abs(ringIndex - nextRingIndex));
            steps = findMinRotateSteps(nextRingIndex, keyIndex + 1, key, map, len, cache);
            minSteps = Math.min(minSteps, distance + steps + 1);
        }
        cache[ringIndex][keyIndex] = minSteps;
        return minSteps;
    }
}
```

## 3. Time & Space Complexity

**DFS:** 时间复杂度O(n ^ m), 空间复杂度O(n)

**DFS + Memoization:** 时间复杂度O(m^2 \* n), m为ring的长度, n为key的长度, 空间复杂度O(mn)


---

# 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://protegejj.gitbook.io/algorithm-practice/leetcode/dynamic-programming/514-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.