Approach 1: Dynamic Programming, Top-Down
from functools import lru_cache
class Solution:
def findRotateSteps(self, ring: str, key: str) -> int:
@lru_cache(None)
def findMinSteps(r, key):
if key == "":
return 0
res = float("inf")
for i, c in enumerate(ring):
if c == key[0]:
min_dist = min(
abs(r - i), # anti-clockwise
len(ring) - abs(r - i) # clockwise
)
res = min(res, 1 + min_dist + findMinSteps(i, key[1:]))
return res
return findMinSteps(0, key)Complexity
Time:
Space:
Notes
Approach 2: Dynamic Programming, Bottom-Up
Complexity
TODO