Leetcode Freedom Trail problem solution

In this Leetcode Freedom Trail problem solution 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]:

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

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.

Problem solution in Python.

class Solution:
    def findRotateSteps(self, a: str, pat: str) -> int:

        n = len(a)
        m = len(pat)
        
        # next_counterclockwise
        next_left = defaultdict(dict)
        
        for i in chain(range(n), range(n)):
            next_left[i] = copy.copy(next_left[(i-1)%n])
            next_left[i][a[i]] = i
        
        # next_clockwise
        next_right = defaultdict(dict)
        
        for i in chain(reversed(range(n)), reversed(range(n))):
            next_right[i] = copy.copy(next_right[(i+1)%n])
            next_right[i][a[i]] = i
            
        @lru_cache(None)
        def recurse(i, j):
            if j == m:
                return 0
            else:
                c = pat[j]
                left_pos = next_left[i][c]
                right_pos = next_right[i][c]
                
                left = (i - left_pos) % n + 1 + recurse(left_pos, j+1)
                right = (right_pos - i) % n + 1 + recurse(right_pos, j+1)
                
                return min(left, right)
        
        return recurse(0, 0)

Problem solution in Java.

public int findRotateSteps(String ring, String key) {
        return dfs(ring.toCharArray(), 0, key.toCharArray(), 0, new int[ring.length()][key.length()]);
    }
    
    private int dfs(char[] ring, int pos, char[] key, int idx, int[][] mem) {
        if (idx == key.length) 
            return 0;
        if (mem[pos][idx] > 0) 
            return mem[p][idx];
        int minSteps = Integer.MAX_VALUE;
        for (int i = 0; i < ring.length; i++) {
            if (ring[i] == key[idx]) {
                int distance = Math.min(Math.abs(i - pos), ring.length - Math.abs(i - pos));
                minSteps = Math.min(minSteps, distance + 1 + dfs(ring, i, key, idx + 1, mem));
            }
        }
        mem[pos][idx] = minSteps;
        return mem[pos][idx];
    }

Problem solution in C++.

class Solution {
public:
    vector<vector<int>>dp;
    int n, m;
    int solve(string &ring, string &key, int r, int k){
        if(k == m)
            return 0;
        if(dp[r][k] != -1)return dp[r][k];
        int cnt = 0;
        int ans = 0;
        while(cnt < n){//clockwise
            if(ring[(r + cnt)%n] == key[k]){
                ans += (cnt + solve(ring, key, (r + cnt)%n, k + 1));
                break;
            }
            cnt++;
        }
        cnt = n - 1;
        while(cnt >= 0){//anticlockwise
            if(ring[(r + cnt)%n] == key[k]){
                ans = min(ans, (n - cnt) + solve(ring, key, (r + cnt)%n, k + 1));
                break;
            }
            cnt--;
        }
        return dp[r][k] = ans;
    }
    int findRotateSteps(string ring, string key) {
        n = ring.size();
        m = key.size();
        dp.resize(n + 1, vector<int>(m + 1, -1));
        int ans = solve(ring, key, 0, 0) + key.size();
        return ans;
    }
};

coding problems solutions