514. 自由之路

514. 自由之路

class FindRotateSteps:
    """
    514. 自由之路
    https://leetcode.cn/problems/freedom-trail/
    """
    def solution(self, ring: str, key: str) -> int:
        m, n = len(ring), len(key)
        # 字符 -> 索引列表
        self.charToIndex = dict()
        self.memo = [[0 for _ in range(n)] for _ in range(m)]
        for idx, c in enumerate(ring):
            if c not in self.charToIndex:
                self.charToIndex[c] = []
            self.charToIndex.get(c).append(idx)
        return self.dp(ring, 0, key, 0)

    def dp(self, ring, i, key, j):
        """
        计算圆盘指针在 ring[i]，输⼊ key[j..] 的最少操作数
        :param ring:
        :param i:
        :param key:
        :param j:
        :return:
        """
        m, n = len(ring), len(key)
        if j == n:
            return 0
        if self.memo[i][j] != 0:
            return self.memo[i][j]

        res = float('inf')

        # 做选择
        # ring 上可能有多个字符 key[j]
        for k in self.charToIndex[key[j]]:
            # 拨动指针的次数
            delta = abs(i - k)
            # 选择顺时针还是逆时针
            delta = min(delta, m-delta)
            # 将指针拨到 ring[k]，继续输⼊ key[j+1..]
            subproblem = self.dp(ring, k, key, j+1)
            # 选择「整体」操作次数最少的
            # 加⼀是因为按动按钮也是⼀次操作
            res = min(res, 1 + delta + subproblem)

        # 将结果存⼊备忘录
        self.memo[i][j] = res
        return res


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