Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/514.html

514. Freedom Trail

Level

Hard

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 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:

Image text

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.

Solution

Use dynamic programming. Use a map to store each letter and the indices of the letter in ring. Create an array dp of length ring.length(), which is initialized so that all elements are INFINITY. The index in ring is initially 0. For each letter in key, if it is the first letter, simply find the indices of the first letter and update the indices’ steps. Otherwise, check whether the current letter is the same as the previous letter. If so, then only pressing is needed, so update the indices’ steps by 1. Otherwise, use the previous indices and their steps to update the current indices’ steps. Finally, loop over dp and find the minimum value to return.

  • class Solution {
    public int findRotateSteps(String ring, String key) {
        final int INFINITY = Integer.MAX_VALUE / 10;
        Map<Character, List<Integer>> map = new HashMap<Character, List<Integer>>();
        int ringLength = ring.length(), keyLength = key.length();
        for (int i = 0; i < ringLength; i++) {
            char c = ring.charAt(i);
            List<Integer> list = map.getOrDefault(c, new ArrayList<Integer>());
            list.add(i);
            map.put(c, list);
        }
        int[] dp = new int[ringLength];
        Arrays.fill(dp, INFINITY);
        dp[0] = 0;
        for (int i = 0; i < keyLength; i++) {
            List<Integer> prevList = i == 0 ? new ArrayList<Integer>(Arrays.asList(0)) : map.get(key.charAt(i - 1));
            char prevC = i == 0 ? ring.charAt(0) : key.charAt(i - 1);
            char currC = key.charAt(i);
            if (prevC == currC) {
                for (int prevIndex : prevList)
                    dp[prevIndex]++;
            } else {
                List<Integer> currList = map.get(currC);
                for (int currIndex : currList) {
                    for (int prevIndex : prevList) {
                        int difference = Math.abs(currIndex - prevIndex);
                        dp[currIndex] = Math.min(dp[currIndex], 1 + dp[prevIndex] + Math.min(difference, ringLength - difference));
                    }
                }
                for (int prevIndex : prevList)
                    dp[prevIndex] = INFINITY;
            }
        }
        int minSteps = INFINITY;
        for (int steps : dp)
            minSteps = Math.min(minSteps, steps);
        return minSteps;
    }
}

  • // OJ: https://leetcode.com/problems/freedom-trail/
// Time: O(N * M^2)
// Space: O(MN)
// Ref: https://leetcode.com/problems/freedom-trail/discuss/98902/Concise-Java-DP-Solution
class Solution {
public:
    int findRotateSteps(string ring, string key) {
        int M = ring.size(), N = key.size();
        vector<vector<int>> dp(N + 1, vector<int>(M));
        for (int i = N - 1; i >= 0; --i) {
            for (int j = 0; j < M; ++j) {
                dp[i][j] = INT_MAX;
                for (int k = 0; k < M; ++k) {
                    if (ring[k] != key[i]) continue;
                    int diff = abs(j - k);
                    int step = min(diff, M - diff);
                    dp[i][j] = min(dp[i][j], step + dp[i + 1][k]);
                }
            }
        }
        return dp[0][0] + N;
    }
};

  • import collections


class Solution(object):
  def findRotateSteps(self, ring, key):
    """
    :type ring: str
    :type key: str
    :rtype: int
    """

    def dfs(ring, key, pointTo, d, length, cache):
      if (pointTo, key) in cache:
        return cache[pointTo, key]
      if not key:
        return 0
      minDist = float("inf")
      toChar = key[0]
      for i in d[toChar]:
        cost = min(length - abs(pointTo - i), abs(pointTo - i)) + 1
        cost += dfs(ring, key[1:], i, d, length, cache)
        minDist = min(minDist, cost)
      cache[pointTo, key] = minDist
      return minDist

    cache = {}
    d = collections.defaultdict(list)
    for i, c in enumerate(ring):
      d[c].append(i)
    length = len(ring)
    return dfs(ring, key, 0, d, length, cache)


  • func findRotateSteps(ring string, key string) int {
	m, n := len(key), len(ring)
	pos := [26][]int{}
	for j, c := range ring {
		pos[c-'a'] = append(pos[c-'a'], j)
	}
	f := make([][]int, m)
	for i := range f {
		f[i] = make([]int, n)
		for j := range f[i] {
			f[i][j] = 1 << 30
		}
	}
	for _, j := range pos[key[0]-'a'] {
		f[0][j] = min(j, n-j) + 1
	}
	for i := 1; i < m; i++ {
		for _, j := range pos[key[i]-'a'] {
			for _, k := range pos[key[i-1]-'a'] {
				f[i][j] = min(f[i][j], f[i-1][k]+min(abs(j-k), n-abs(j-k))+1)
			}
		}
	}
	ans := 1 << 30
	for _, j := range pos[key[m-1]-'a'] {
		ans = min(ans, f[m-1][j])
	}
	return ans
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

func abs(x int) int {
	if x < 0 {
		return -x
	}
	return x
}

All Problems

All Solutions