Freedom Trail LeetCode solution in Python

1
class Solution:
2
    def findRotateSteps(self, ring: str, key: str) -> int:
3
        locs = {}
4
        for i, ch in enumerate(ring):
5
            locs.setdefault(ch, []).append(i)
6

7
        @cache
8
        def fn(i, j):
9
            """Return turns to finish key[j:] startin from ith position on ring."""
10
            if j == len(key):
11
                return 0
12
            loc = locs[key[j]]
13
            k = bisect_left(loc, i) % len(loc)
14
            ans = min(abs(i - loc[k]), len(ring) - abs(i - loc[k])) + fn(loc[k], j + 1)
15
            k = (k - 1) % len(loc)
16
            ans = min(
17
                ans,
18
                min(abs(i - loc[k]), len(ring) - abs(i - loc[k])) + fn(loc[k], j + 1),
19
            )
20
            return ans
21

22
        return fn(0, 0) + len(key)