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] 仅由若干位数字组成

解题思路

这是一道典型的求最短路径问题，可以用BFS（广度优先搜索）来解决。

基本思路：

  1. 将问题建模为图论问题：从"0000"到target的最短路径
  2. 每个状态（4位数字串）是图中的一个节点
  3. 相邻状态之间有边相连（每次只能改变一位数字，且只能+1或-1）
  4. deadends中的状态不能访问，相当于图中的障碍点

算法步骤：

  1. 初始化队列，将起始状态"0000"加入队列（如果不在deadends中）
  2. 使用BFS遍历所有可能的状态：
    • 对于当前状态，生成所有相邻状态（8个：每位数字+1/-1）
    • 数字0的前一个是9，数字9的下一个是0（环形）
    • 跳过已访问的状态和deadends中的状态
    • 如果找到目标状态，返回步数
  3. 如果队列为空仍未找到目标，返回-1

复杂度考虑：

  • 状态空间大小：10^4 = 10000个可能的状态
  • 每个状态最多有8个相邻状态
  • BFS保证找到的是最短路径

这是一个经典的状态空间搜索问题，BFS是最优解法。

代码实现

class Solution {
public:
    int openLock(vector<string>& deadends, string target) {
        unordered_set<string> dead(deadends.begin(), deadends.end());
        if (dead.count("0000")) return -1;
        if (target == "0000") return 0;
        
        queue<string> q;
        unordered_set<string> visited;
        q.push("0000");
        visited.insert("0000");
        
        int steps = 0;
        
        while (!q.empty()) {
            int size = q.size();
            steps++;
            
            for (int i = 0; i < size; i++) {
                string curr = q.front();
                q.pop();
                
                // 生成8个相邻状态
                for (int j = 0; j < 4; j++) {
                    string next1 = curr, next2 = curr;
                    // 向上拨动
                    next1[j] = (curr[j] - '0' + 1) % 10 + '0';
                    // 向下拨动
                    next2[j] = (curr[j] - '0' + 9) % 10 + '0';
                    
                    for (string next : {next1, next2}) {
                        if (next == target) return steps;
                        if (!visited.count(next) && !dead.count(next)) {
                            visited.insert(next);
                            q.push(next);
                        }
                    }
                }
            }
        }
        
        return -1;
    }
};

class Solution:
    def openLock(self, deadends: List[str], target: str) -> int:
        dead = set(deadends)
        if "0000" in dead:
            return -1
        if target == "0000":
            return 0
        
        queue = collections.deque(["0000"])
        visited = {"0000"}
        steps = 0
        
        while queue:
            steps += 1
            for _ in range(len(queue)):
                curr = queue.popleft()
                
                # 生成8个相邻状态
                for i in range(4):
                    digit = int(curr[i])
                    # 向上拨动和向下拨动
                    for move in [1, -1]:
                        new_digit = (digit + move) % 10
                        next_state = curr[:i] + str(new_digit) + curr[i+1:]
                        
                        if next_state == target:
                            return steps
                        if next_state not in visited and next_state not in dead:
                            visited.add(next_state)
                            queue.append(next_state)
        
        return -1

public class Solution {
    public int OpenLock(string[] deadends, string target) {
        HashSet<string> dead = new HashSet<string>(deadends);
        if (dead.Contains("0000")) return -1;
        if (target == "0000") return 0;
        
        Queue<string> queue = new Queue<string>();
        HashSet<string> visited = new HashSet<string>();
        queue.Enqueue("0000");
        visited.Add("0000");
        
        int steps = 0;
        
        while (queue.Count > 0) {
            int size = queue.Count;
            steps++;
            
            for (int i = 0; i < size; i++) {
                string curr = queue.Dequeue();
                
                // 生成8个相邻状态
                for (int j = 0; j < 4; j++) {
                    char[] chars1 = curr.ToCharArray();
                    char[] chars2 = curr.ToCharArray();
                    
                    // 向上拨动
                    chars1[j] = (char)('0' + (curr[j] - '0' + 1) % 10);
                    // 向下拨动
                    chars2[j] = (char)('0' + (curr[j] - '0' + 9) % 10);
                    
                    string[] nextStates = {new string(chars1), new string(chars2)};
                    
                    foreach (string next in nextStates) {
                        if (next == target) return steps;
                        if (!visited.Contains(next) && !dead.Contains(next)) {
                            visited.Add(next);
                            queue.Enqueue(next);
                        }
                    }
                }
            }
        }
        
        return -1;
    }
}

var openLock = function(deadends, target) {
    const deadSet = new Set(deadends);
    if (deadSet.has("0000")) return -1;
    if (target === "0000") return 0;
    
    const queue = [["0000", 0]];
    const visited = new Set(["0000"]);
    
    const getNeighbors = (code) => {
        const neighbors = [];
        for (let i = 0; i < 4; i++) {
            const digit = parseInt(code[i]);
            const up = (digit + 1) % 10;
            const down = (digit + 9) % 10;
            neighbors.push(code.substring(0, i) + up + code.substring(i + 1));
            neighbors.push(code.substring(0, i) + down + code.substring(i + 1));
        }
        return neighbors;
    };
    
    while (queue.length > 0) {
        const [current, steps] = queue.shift();
        
        for (const neighbor of getNeighbors(current)) {
            if (neighbor === target) return steps + 1;
            if (!deadSet.has(neighbor) && !visited.has(neighbor)) {
                visited.add(neighbor);
                queue.push([neighbor, steps + 1]);
            }
        }
    }
    
    return -1;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(10^4) = O(1)，最多需要遍历所有10000个可能的状态，每个状态生成8个邻居状态的时间为常数
空间复杂度O(10^4) = O(1)，主要用于存储visited集合、队列和deadends集合，最多存储10000个状态

相关题目