Freedom Trail Problem

Problem

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.

Examples

Example 1:

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

Solution

Method 1 - Recursion

We will be searching key in ring, starting from first character. The idea is - we can either go

• clockwise, OR
• anticlockwise in the ring

And choose the index or distance whichever is shorter. In a way, we are treating ring as in circular string.

• When we move ring anti-clockwise, our search is actually clockwise or from start of string.
• When we move ring clockwise, our search is actually anti-clockwise OR from end of string

For eg. when we search for d:

Algorithm

1. Search for chars in key in ring - both from start and end of string
2. Choose min between them, and start with next character in key
3. Now, we chosen optimal char, that means our string has changed it being circular,
4. Repeat the steps 1-3, till we reach end of key

Code

But time complexity is super high, so lets go to method 2 which uses memoization.

Complexity

• Time: O(2^N)
• Space: O(1)

Method 2 - Using Memoization

Code

Java

class Solution {
    Map<String, Integer> memo = new HashMap<>();
    public int findRotateSteps(String ring, String key) {
        return dfs(ring, key, 0);
    }

    private int dfs(String ring, String key, int i){
        if(i == key.length()) {
            return 0;
        }
        int ans = 0;
        char ch = key.charAt(i);
        String mapKey = ring + "--" + i;
        if(memo.containsKey(mapKey)) {
            return memo.get(mapKey);
        }

        int f = ring.indexOf(ch); // clockwise
        int b = ring.lastIndexOf(ch); // anti-clockwise
        int forward = 1 +f + dfs(ring.substring(f) + ring.substring(0, f), key, i+1);
        int back = 1 + ring.length() - b + dfs(ring.substring(b) + ring.substring(0, b),key, i+1);
        ans = Math.min(forward, back);
        memo.put(mapKey, ans);
        return ans;
    }    

}

Complexity

• Time: O(R * K) - where R is length of ring, and K is length of key. As in our DFS, we go K steps deep, and each string, we take O(n) to find key character, and create a new string
• Space: O(R*K) - As we use memo map