514. Freedom Trail

[zeikar]

Problem link

https://leetcode.com/problems/freedom-trail

Problem Summary

ring와 입력해야 할 key가 주어질 때 최소 횟수로 ring을 돌려서 key를 만드는 횟수를 구하는 문제

Solution

간단한 DP로 풀 수 있다. 현재 위치 기준으로 왼쪽, 오른쪽으로 돌려가며 찾을 수 있다.
시간 복잡도는 O(R^2 K)

다른 솔루션?

left, right로 돌릴 때의 문자열을 찾을 때 전처리를 통해 미리 구해놓으면 더 빨리 구할 수 있다. 또는, 에디토리얼 보니까 다익스트라로도 가능하다고 한다.

Source Code

class Solution:
    def findRotateSteps(self, ring: str, key: str) -> int:
        n = len(ring)
        k = len(key)
        
        @cache
        def rotate(keyIndex, ringIndex):
            if keyIndex == k:
                return 0

            ans = 987654321
            # left
            for i in range(n):
                ri = (ringIndex + n - i) % n
                if ring[ri] == key[keyIndex]:
                    ans = min(ans, rotate(keyIndex + 1, ri) + i + 1)
                    break
            
            # right
            for i in range(n):
                ri = (ringIndex + i) % n
                if ring[ri] == key[keyIndex]:
                    ans = min(ans, rotate(keyIndex + 1, ri) + i + 1)
                    break

            return ans

        return rotate(0, 0)