1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
|
# 514. Freedom Trail
from collections import defaultdict
"""
in the video game fallout 4, the quest road to freedom requires players to
reach a metal dial called the freedom trail ring and use the dial to spell a
specific keyword to open the door. given a string 'ring' that represents the
code engraved on the outer ring and anotherstring 'key' that represents the
keyword that needs to be spelled, return the minimum number of steps to spell
all the characters in keyword. initially, the first character of the ring is
aligned at the "12:00" direction. you should spell all the characters in
'key' one by one by rotating 'ring' clockwise or counterclockwise to make
each character of the string 'key' aligned at the "12:00" direction and then
by pressing the centre button.
"""
class Solution(object):
def findRotateSteps(self, ring, key):
"""
:type ring: str
:type key: str
:rtype: int
"""
idx, n, dp, pre = (
defaultdict(list),
len(ring),
[0] * len(ring),
key[0],
)
for i, c in enumerate(ring):
idx[c].append(i)
for i in idx[key[0]]:
dp[i] = min(i, n - i) + 1
for c in key[1:]:
for i in idx[c]:
dp[i] = (
min(
(
dp[j] + min(i - j, j + n - i)
if i >= j
else dp[j] + min(j - i, i + n - j)
)
for j in idx[pre]
)
+ 1
)
pre = c
return min(dp[i] for i in idx[key[-1]])
if __name__ == "__main__":
obj = Solution()
print(obj.findRotateSteps("godding", "gd"))
print(obj.findRotateSteps("godding", "godding"))
|