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

```
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 steps = findMinRotateSteps(0, 0, key, map, m, 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)