打开转盘锁 -- BFS

打开转盘锁
这里提供两种实现，单向BFS和双向BFS。

关于双向BFS介绍：双向BFS

class OpenLock:
    """
    752. 打开转盘锁
    https://leetcode.cn/problems/open-the-lock/
    """
    def solution(self, deadends: List[str], target: str) -> int:
        """
        单向BFS
        :param deadends: 
        :param target: 
        :return: 
        """
        visited = set()
        # 将deadends初始化到visited数组中
        for deadend in deadends:
            visited.add(deadend)

        queue = []
        step = 0
        queue.append('0000')
        visited.add('0000')

        while queue:
            sz = len(queue)
            for i in range(sz):
                cur = queue.pop(0)

                if cur == target:
                    return step

                if cur in visited:
                    continue

                visited.add(cur)

                for j in range(4):
                    up = self.plusOne(cur, j)
                    if up not in visited:
                        queue.append(up)

                    down = self.minusOne(cur, j)
                    if down not in visited:
                        queue.append(down)

            step += 1
        return -1

    def plusOne(self, cur, j):
        if cur[j] == '9':
            return cur[:j] + '0' + cur[j+1:]
        else:
            return cur[:j] + str(int(cur[j])+1) + cur[j+1:]

    def minusOne(self, cur, j):
        if cur[j] == '0':
            return cur[:j] + '9' + cur[j + 1:]
        else:
            return cur[:j] + str(int(cur[j]) - 1) + cur[j + 1:]

    def solution2(self, deadends: List[str], target: str) -> int:
        """
        双向BFS优化
        :param deadends: 
        :param target: 
        :return: 
        """
        deads = set()
        visited = set()
        # 将deadends初始化到visited数组中
        for deadend in deadends:
            deads.add(deadend)

        q1 = set()
        q2 = set()
        q1.add('0000')
        q2.add(target)
        step = 0

        while q1 and q2:
            # 额外优化
            if len(q1) > len(q2):
                tmp = q1
                q1 = q2
                q2 = tmp

            temp = set()
            for cur in q1:
                if cur in deads:
                    continue
                if cur in q2:
                    return step

                visited.add(cur)

                for j in range(4):
                    up = self.plusOne(cur, j)
                    if up not in visited:
                        temp.add(up)

                    down = self.minusOne(cur, j)
                    if down not in visited:
                        temp.add(down)

            step += 1
            # 这里temp相当于q1，交换q1和q2
            q1 = q2
            q2 = temp

        return -1


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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112