打开转盘锁

标签: 广度优先搜索 数组 哈希表 字符串

难度: Medium

你有一个带有四个圆形拨轮的转盘锁。每个拨轮都有10个数字： '0', '1', '2', '3', '4', '5', '6', '7', '8', '9' 。每个拨轮可以自由旋转：例如把 '9' 变为 '0'，'0' 变为 '9' 。每次旋转都只能旋转一个拨轮的一位数字。

锁的初始数字为 '0000' ，一个代表四个拨轮的数字的字符串。

列表 deadends 包含了一组死亡数字，一旦拨轮的数字和列表里的任何一个元素相同，这个锁将会被永久锁定，无法再被旋转。

字符串 target 代表可以解锁的数字，你需要给出解锁需要的最小旋转次数，如果无论如何不能解锁，返回 -1 。

示例 1:

输入：deadends = ["0201","0101","0102","1212","2002"], target = "0202"
输出：6
解释：
可能的移动序列为 "0000" -> "1000" -> "1100" -> "1200" -> "1201" -> "1202" -> "0202"。
注意 "0000" -> "0001" -> "0002" -> "0102" -> "0202" 这样的序列是不能解锁的，
因为当拨动到 "0102" 时这个锁就会被锁定。

示例 2:

输入: deadends = ["8888"], target = "0009"
输出：1
解释：把最后一位反向旋转一次即可 "0000" -> "0009"。

示例 3:

输入: deadends = ["8887","8889","8878","8898","8788","8988","7888","9888"], target = "8888"
输出：-1
解释：无法旋转到目标数字且不被锁定。

提示：

  • 1 <= deadends.length <= 500
  • deadends[i].length == 4
  • target.length == 4
  • target 不在 deadends 之中
  • target 和 deadends[i] 仅由若干位数字组成

Submission

运行时间: 864 ms

内存: 15.8 MB

from typing import List
from collections import deque


class Solution:
    def openLock(self, deadends: List[str], target: str) -> int:
        def up(s, i):
            arr = list(s)
            if arr[i] == '9':
                arr[i] = '0'
            else:
                arr[i] = str(int(arr[i]) + 1)
            return ''.join(arr)

        def down(s, i):
            arr = list(s)
            if arr[i] == '0':
                arr[i] = '9'
            else:
                arr[i] = str(int(arr[i]) - 1)
            return ''.join(arr)

        q = deque()
        visited = set(deadends)
        if '0000' in visited:
            return -1
        q.append("0000")
        visited.add("0000")
        count = 0
        while q:
            size = len(q)
            for _ in range(size):
                s = q.popleft()
                if s == target:
                    return count
                for i in range(4):
                    for func in (up, down):
                        n = func(s, i)
                        if n not in visited:
                            visited.add(n)
                            q.append(n)
            count += 1
        return -1


if __name__ == '__main__':
    s = Solution()
    print(s.openLock(["0201","0101","0102","1212","2002"], '0202'))

Explain

此题解采用了宽度优先搜索（BFS）算法来找到从初始状态'0000'到目标状态'target'的最短路径。每个状态表示为一个四位数字的字符串，每次操作可以将任意一位数字增加1或减少1。如果增加或减少后的数字是9或者0，则会循环到0或9。使用队列来存储每一层的所有状态，并用一个集合来记录已访问过的状态和死亡数字。从'0000'开始搜索，每次从队列中取出当前状态，并生成新的状态，如果新状态没有被访问过且不在死亡数字中，则加入队列继续搜索。如果找到目标状态，则返回当前的步数。如果队列为空还没有找到目标状态，返回-1。

时间复杂度: O(N)

空间复杂度: O(N)

from typing import List
from collections import deque


class Solution:
    def openLock(self, deadends: List[str], target: str) -> int:
        def up(s, i):
            arr = list(s)
            if arr[i] == '9':
                arr[i] = '0'
            else:
                arr[i] = str(int(arr[i]) + 1)
            return ''.join(arr)

        def down(s, i):
            arr = list(s)
            if arr[i] == '0':
                arr[i] = '9'
            else:
                arr[i] = str(int(arr[i]) - 1)
            return ''.join(arr)

        q = deque()
        visited = set(deadends)
        if '0000' in visited:
            return -1
        q.append('0000')
        visited.add('0000')
        count = 0
        while q:
            size = len(q)
            for _ in range(size):
                s = q.popleft()
                if s == target:
                    return count
                for i in range(4):
                    for func in (up, down):
                        n = func(s, i)
                        if n not in visited:
                            visited.add(n)
                            q.append(n)
            count += 1
        return -1

if __name__ == '__main__':
    s = Solution()
    print(s.openLock(['0201','0101','0102','1212','2002'], '0202'))

Explore

在宽度优先搜索（BFS）中使用队列而不是栈是因为队列遵循先进先出（FIFO）的原则，这有助于按层次（从起点开始的距离）探索所有可能的状态。这种方式确保了一旦找到目标状态，就是通过最短的路径达到的。相反，栈遵循后进先出（LIFO）的原则，它会导致深度优先搜索（DFS），这种搜索方式首先探索尽可能深的路径而不是最短路径，可能会错过最短路径解，在解决此类找最短路径的问题时不是最佳选择。

是的，在BFS中，由于搜索是层次进行的，当首次到达某个状态时，可以保证是通过最短路径到达的。因此，一旦在搜索过程中遇到目标状态，立即返回的步数即是到达该状态的最短路径。此时无需考虑其他可能的路径，因为它们要么已经被探索过，要么路径更长。

函数`up`和`down`处理边界条件的策略是，当需要增加数字9时，它会回绕到0，而当需要减少数字0时，它会回绕到9。这种处理方式是对转盘锁的自然模拟，因为转盘锁是循环的。这种处理方式是最优的，因为它正确并且直接地反映了问题的实际物理约束。

如果'0000'在deadends列表中，意味着初始状态是锁定状态，无法开始任何操作来改变锁的状态。在这种情况下，由于起始点已被阻塞，不存在任何可能的路径可以从'0000'达到目标状态。因此，直接返回-1是合理的，表示问题无解。