Freedom Trail

Intuition

Solution

class Solution:
    def findRotateSteps(self, ring: str, key: str) -> int:
        n = len(ring)
        steps = [(1 + min(i, n - i)) for i in range(n)]
        last = [i for i in range(n) if ring[i] == key[0]]
        for c in key[1:]:
            tmp = []
            i = 0
            for j in range(n):
                if ring[j] == c:
                    while True:
                        lo = last[i-1]
                        hi = last[i]
                        if lo >= hi and (j >= lo or j <= hi):
                            break
                        elif lo <= j <= hi:
                            break
                        i = (i + 1) % len(last)
                    steps[j] = min(
                        steps[lo] + ((j - lo) if j >= lo else (j + n - lo)),
                        steps[hi] + ((hi - j) if hi >= j else (hi + n - j))
                    ) + 1
                    tmp.append(j)
            last = tmp
        return min([steps[i] for i in last])