514. Freedom Trail

Difficulty:
Related Topics:
Similar Questions:

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

      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:

    Solution

    /**
     * @param {string} ring
     * @param {string} key
     * @return {number}
     */
    var findRotateSteps = function(ring, key) {
        var next = function(i) {
            return i === ring.length - 1 ? 0 : i + 1;
        };
        var prev = function(i) {
            return i === 0 ? ring.length - 1 : i - 1;
        };
        var dp = Array(ring.length).fill(0).map(() => Array(key.length));
        var dfs = function(i, j) {
            if (j === key.length) return 0;
            if (dp[i][j] !== undefined) return dp[i][j];
            if (ring[i] === key[j]) {
                dp[i][j] = 1 + dfs(i, j + 1);
                return dp[i][j];
            }
            var nextI = next(i);
            while (ring[nextI] !== key[j]) nextI = next(nextI);
            var prevI = prev(i);
            while (ring[prevI] !== key[j]) prevI = prev(prevI);
            dp[i][j] = Math.min(
                ((nextI - i + ring.length) % ring.length) + dfs(nextI, j),
                ((i - prevI + ring.length) % ring.length) + dfs(prevI, j),
            );
            return dp[i][j];
        };
        return dfs(0, 0);
    };
    

    Explain:

    nope.

    Complexity: