{x}
blog image

Freedom Trail

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.

 

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

 

Constraints:

  • 1 <= ring.length, key.length <= 100
  • ring and key consist of only lower case English letters.
  • It is guaranteed that key could always be spelled by rotating ring.

Solution Explanation: Freedom Trail

This problem asks for the minimum number of steps to spell a key string using a rotating ring string. Each step involves either rotating the ring one position clockwise or counter-clockwise, or pressing the center button to "spell" the currently aligned character.

The optimal solution uses dynamic programming. We build a DP table to store the minimum steps to spell a prefix of the key string, given the position of a specific character in the ring is currently aligned.

1. Preprocessing:

  • We create a dictionary (or array) pos to store the indices of each character in ring. This allows for quick lookup of character positions.

2. DP Table:

  • f[i][j] represents the minimum steps to spell the first i+1 characters of key, with the j-th character of ring currently aligned.

3. Base Case:

  • f[0][j] (for all j where ring[j] == key[0]): The minimum steps to spell the first character key[0]. This is min(j, n - j) + 1, where n is the length of ring. min(j, n - j) is the minimum rotations needed to align key[0], and +1 is for pressing the button to spell it.

4. Recurrence Relation:

  • For i > 0, we calculate f[i][j] (for all j where ring[j] == key[i]):
    • We iterate through all possible positions k where key[i-1] appears in ring.
    • f[i][j] = min(f[i][j], f[i-1][k] + min(abs(j-k), n - abs(j-k)) + 1)
    • This means the minimum steps to spell key[0...i] with ring[j] aligned is the minimum of all possible transitions from positions k of key[i-1] to position j of key[i]. The transition cost is the rotations (min(abs(j-k), n - abs(j-k))) plus the button press (+1).

5. Result:

  • The final answer is the minimum value in the last row of the DP table (f[m-1], where m is the length of key), as this represents the minimum steps to spell the entire key string.

Time Complexity: O(m * n^2), where m is the length of key and n is the length of ring. This is because the nested loops iterate through all pairs of positions in key and ring.

Space Complexity: O(m * n) to store the DP table.

Code Examples (Python):

from collections import defaultdict
 
def findRotateSteps(ring: str, key: str) -> int:
    m, n = len(key), len(ring)
    pos = defaultdict(list)  # Preprocess character positions
    for i, c in enumerate(ring):
        pos[c].append(i)
 
    f = [[float('inf')] * n for _ in range(m)]  # DP table initialization
 
    for j in pos[key[0]]:  # Base Case
        f[0][j] = min(j, n - j) + 1
 
    for i in range(1, m):
        for j in pos[key[i]]:
            for k in pos[key[i - 1]]:
                f[i][j] = min(f[i][j], f[i - 1][k] + min(abs(j - k), n - abs(j - k)) + 1)
 
    return min(f[m - 1][j] for j in pos[key[m - 1]])

The code in other languages (Java, C++, Go, TypeScript) follow a very similar structure, with minor syntactic differences. The core DP logic remains the same.