514. Freedom Trail - Explanation

class Solution:
    def findRotateSteps(self, ring: str, key: str) -> int:
        def dfs(r, k):
            if k == len(key):
                return 0

            res = float("inf")
            for i, c in enumerate(ring):
                if c == key[k]:
                    min_dist = min(abs(r - i), len(ring) - abs(r - i))
                    res = min(res, min_dist + 1 + dfs(i, k + 1))
            return res

        return dfs(0, 0)

class Solution:
    def findRotateSteps(self, ring: str, key: str) -> int:
        n = len(ring)
        m = len(key)
        dp = {}

        def dfs(r, k):
            if k == m:
                return 0
            if (r, k) in dp:
                return dp[(r, k)]

            res = float("inf")
            for i, c in enumerate(ring):
                if c == key[k]:
                    min_dist = min(abs(r - i), n - abs(r - i))
                    res = min(res, min_dist + 1 + dfs(i, k + 1))
            dp[(r, k)] = res
            return res

        return dfs(0, 0)

class Solution:
    def findRotateSteps(self, ring: str, key: str) -> int:
        n = len(ring)
        m = len(key)
        dp = [[float("inf")] * n for _ in range(m + 1)]

        for i in range(n):
            dp[m][i] = 0

        for k in range(m - 1, -1, -1):
            for r in range(n):
                for i in range(n):
                    if ring[i] == key[k]:
                        min_dist = min(abs(r - i), n - abs(r - i))
                        dp[k][r] = min(dp[k][r], min_dist + 1 + dp[k + 1][i])

        return dp[0][0]

class Solution:
    def findRotateSteps(self, ring: str, key: str) -> int:
        n = len(ring)
        m = len(key)
        dp = [0] * n

        adj = [[] for _ in range(26)]
        for i in range(n):
            adj[ord(ring[i]) - ord('a')].append(i)

        for k in range(m - 1, -1, -1):
            next_dp = [float("inf")] * n
            for r in range(n):
                for i in adj[ord(key[k]) - ord('a')]:
                    min_dist = min(abs(r - i), n - abs(r - i))
                    next_dp[r] = min(next_dp[r], min_dist + 1 + dp[i])
            dp = next_dp

        return dp[0]

class Solution:
    def findRotateSteps(self, ring: str, key: str) -> int:
        n = len(ring)
        m = len(key)
        dp = [min(i, n - i) for i in range(n)]

        adj = [[] for _ in range(26)]
        for i in range(n):
            adj[ord(ring[i]) - ord('a')].append(i)

        for k in range(1, m):
            for r in adj[ord(key[k]) - ord('a')]:
                min_dist = float("inf")
                for i in adj[ord(key[k - 1]) - ord('a')]:
                    min_dist = min(
                        min_dist,
                        min(abs(r - i), n - abs(r - i)) + dp[i]
                    )
                dp[r] = min_dist

        return min(dp[i] for i in adj[ord(key[-1]) - ord('a')]) + m

class Solution:
    def findRotateSteps(self, ring: str, key: str) -> int:
        n = len(ring)
        m = len(key)

        dp = [0] * n
        next_dp = [0] * n

        adj = [[] for _ in range(26)]
        for i, c in enumerate(ring):
            adj[ord(c) - ord('a')].append(i)

        for k in range(m - 1, -1, -1):
            c = ord(key[k]) - ord('a')
            it, N = 0, len(adj[c])

            for r in range(n):
                if ord(ring[r]) - ord('a') != c:
                    next_dp[r] = float('inf')
                    while it < N and adj[c][it] < r:
                        it += 1

                    nextIdx = adj[c][it] if it < N else adj[c][0]
                    prevIdx = adj[c][it - 1] if it > 0 else adj[c][-1]

                    next_dp[r] = min(
                        (r - prevIdx if r > prevIdx else n - (prevIdx - r)) + dp[prevIdx],
                        (nextIdx - r if nextIdx > r else n - (r - nextIdx)) + dp[nextIdx]
                    )
                else:
                    next_dp[r] = dp[r]

            dp, next_dp = next_dp, dp

        return dp[0] + m