LeetCode 752. 打开转盘锁

Categories:

题目描述
思路分析
1. 解法一：BFS 最短路径（推荐）
相似题目

题目描述

✅ 752. 打开转盘锁

思路分析

解法一：BFS 最短路径（推荐）

核心思路：

四位转盘每次只能转动一位，状态数最多 10^4。

用 BFS 从 “0000” 出发，首次到达目标即最短步数。

通过哈希集合记录死锁与已访问状态。

复杂度分析：

时间复杂度：O(10^4)，每个状态最多扩展一次。

空间复杂度：O(10^4)，队列与集合占用。

class Solution {
    public int openLock(String[] deadends, String target) {
        Set<String> dead = new HashSet<>(Arrays.asList(deadends));
        if (dead.contains("0000")) {
            return -1;
        }

        Deque<String> queue = new ArrayDeque<>();
        queue.offer("0000");
        Set<String> visited = new HashSet<>();
        visited.add("0000");
        int steps = 0;

        // BFS 搜索最短路径
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                String cur = queue.poll();
                if (cur.equals(target)) {
                    return steps;
                }

                for (int pos = 0; pos < 4; pos++) {
                    char[] arr = cur.toCharArray();
                    char c = arr[pos];
                    arr[pos] = c == '9' ? '0' : (char) (c + 1);
                    String up = new String(arr);
                    if (!dead.contains(up) && visited.add(up)) {
                        queue.offer(up);
                    }

                    arr[pos] = c == '0' ? '9' : (char) (c - 1);
                    String down = new String(arr);
                    if (!dead.contains(down) && visited.add(down)) {
                        queue.offer(down);
                    }
                }
            }
            steps++;
        }

        return -1;
    }
}

func openLock(deadends []string, target string) int {
    dead := make(map[string]bool, len(deadends))
    for _, d := range deadends {
        dead[d] = true
    }
    if dead["0000"] {
        return -1
    }

    queue := []string{"0000"}
    visited := map[string]bool{"0000": true}
    steps := 0

    // BFS 搜索最短路径
    for len(queue) > 0 {
        size := len(queue)
        for i := 0; i < size; i++ {
            cur := queue[0]
            queue = queue[1:]
            if cur == target {
                return steps
            }

            for pos := 0; pos < 4; pos++ {
                arr := []byte(cur)
                c := arr[pos]

                arr[pos] = (c-'0'+1)%10 + '0'
                up := string(arr)
                if !dead[up] && !visited[up] {
                    visited[up] = true
                    queue = append(queue, up)
                }

                arr[pos] = (c-'0'+9)%10 + '0'
                down := string(arr)
                if !dead[down] && !visited[down] {
                    visited[down] = true
                    queue = append(queue, down)
                }
            }
        }
        steps++
    }

    return -1
}

相似题目

题目	难度	考察点
433. 最小基因变化	中等	BFS
127. 单词接龙	困难	BFS
773. 滑动谜题	困难	BFS
864. 获取所有钥匙的最短路径	困难	BFS
1091. 二进制矩阵中的最短路径	中等	BFS

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2024/50393373