We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Freedom Trail

Difficulty: Hard

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

Key Insights

  • The ring can be rotated clockwise or anticlockwise by one position, counting as one step.
  • Each character of the key must be matched to a corresponding character on the ring.
  • Pressing the center button to spell a character also counts as a step.
  • Dynamic programming or a breadth-first search can be useful to explore all possible rotations and their corresponding steps.

Space and Time Complexity

Time Complexity: O(N * M^2), where N is the length of key and M is the length of ring.
Space Complexity: O(N * M), due to the DP table storing the steps for each character position.

Solution

To solve the problem, we can use dynamic programming. We'll maintain a 2D array where dp[i][j] represents the minimum steps required to spell the first i characters of the key while the ring is at position j. The algorithm proceeds by iterating through each character of the key, checking all possible positions of the ring that match the current character in the key, and calculating the minimum steps to reach that position from the previous position.

We also need to consider the two possible directions (clockwise and anticlockwise) to reach a character on the ring. The final answer will be the minimum steps to spell the entire key.

Code Solutions

def findRotateSteps(ring: str, key: str) -> int:
    from collections import defaultdict

    # Create a dictionary to store the positions of each character in the ring
    char_positions = defaultdict(list)
    for i, char in enumerate(ring):
        char_positions[char].append(i)

    # DP table: dp[i][j] means the minimum steps to spell key[:i + 1] ending at ring[j]
    dp = [[float('inf')] * len(ring) for _ in range(len(key) + 1)]
    dp[0][0] = 0  # Starting point

    # Fill the DP table
    for i in range(1, len(key) + 1):
        for j in range(len(ring)):
            if key[i - 1] in char_positions:
                for pos in char_positions[key[i - 1]]:
                    # Calculate the distance (steps) to rotate to pos
                    distance = abs(pos - j)
                    distance = min(distance, len(ring) - distance)  # Min of clockwise and anticlockwise
                    dp[i][pos] = min(dp[i][pos], dp[i - 1][j] + distance + 1)  # +1 for pressing the button

    # Get the minimum steps to spell the entire key
    return min(dp[len(key)])
← Back to All Questions