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