Problem of The Day: Freedom Trail

Problem Statement

Intuition

Initially, I think we need to approach this problem recursively, considering each possible rotation step for the ring while trying to match the characters in the key.

Approach

My approach involves using a recursive function dfs to iterate through each character in the key, trying to match it with the characters in the ring. I maintain a memoization dictionary to store the results of already computed subproblems, avoiding redundant calculations.

Complexity

• Time complexity: O(r ^ 2 * k) where r is the length of ring and k is len of key

• Space complexity: O(r * k)

Code

class Solution:
    def findRotateSteps(self, ring: str, key: str) -> int:
        memo = {}
        def dfs(r, k):
            if k == len(key):
                return 0
            if (r, k) in memo:
                return memo[(r, k)]
            res = float('inf')
            for i, c in enumerate(ring):
                if c == key[k]:
                    min_dist = min(
                        abs(i - r), # between
                        len(ring) - abs(i - r) # around
                        ) + 1
                    res = min(res, min_dist + dfs(i, k + 1))
            memo[(r, k)] = res
            return res
        return dfs(0, 0)

Convert to Bottom Up Approach

class Solution:
    def findRotateSteps(self, ring: str, key: str) -> int:
        dp = [0] * len(ring)
        for k in reversed(range(len(key))):
            next_dp = [float('inf')] * len(ring)
            for r in range(len(ring)):
                for i, c in enumerate(ring):
                    if c == key[k]:
                        min_dist = min(
                            abs(i - r),
                            len(ring) - abs(i - r)
                        ) + 1
                        next_dp[r] = min(next_dp[r], min_dist + dp[i])
            dp = next_dp[:]
        return dp[0]