Problem: 752. 打开转盘锁

题目描述

思路及解法

1.用一个集合 deads 存储所有的“死锁”状态，一个集合 visited 存储所有已经访问过的状态，以避免重复访问，一个队列 q 进行广度优先搜索（BFS）;并将 deadends 数组中的每个元素加入 deads 集合。
2.将初始状态 “0000” 加入队列 q 并标记为已访问。

3.进行广度优先搜索（BFS）：

3.1.获取当前队列的大小 sz，表示当前层级中的节点数。
3.2.遍历当前层级中的每个节点：

3.2.1.从队列中取出一个节点 cur。如果 cur 在 deads 中，则跳过该节点。如果 cur 等于目标状态 target，则返回当前步数 step。
3.2.2.生成当前状态 cur 的所有相邻状态（每一位向上拨或向下拨）：对于每个相邻状态 up 和 down，如果尚未访问过，则加入队列并标记为已访问，最后使得步数step++

复杂度

时间复杂度:

$O(N\times M)$;其中$N$为状态空间0000 - 9999，$M$为每个状态的子节点树（即为8.具体到本题中可以认为时间复杂度为常量级别，同理空间复杂度也为常量级别）

空间复杂度:

$O(N)$

Code

class Solution {
    /**
     * Open the Lock
     *
     * @param deadends Given string
     * @param target   Given string
     * @return int
     */
    public int openLock(String[] deadends, String target) {
        // Record the death password to be skipped
        Set<String> deads = new HashSet<>();
        for (String s : deadends) {
            deads.add(s);
        }
        // Record passwords that have been exhausted to prevent backtracking
        Set<String> visited = new HashSet<>();
        Queue<String> q = new LinkedList<>();
        // Start breadth-first search from the starting point
        int step = 0;
        q.offer("0000");
        visited.add("0000");

        while (!q.isEmpty()) {
            int sz = q.size();
            // Spreads all nodes in the current queue around
            for (int i = 0; i < sz; ++i) {
                String cur = q.poll();
                // Determine whether the destination is reached
                if (deads.contains(cur)) {
                    continue;
                }
                if (cur.equals(target)) {
                    return step;
                }

                // Adds the untraversed adjacents of a node to the queue
                for (int j = 0; j < 4; ++j) {
                    String up = plusOne(cur, j);
                    if (!visited.contains(up)) {
                        q.offer(up);
                        visited.add(up);
                    }
                    String down = minusOne(cur, j);
                    if (!visited.contains(down)) {
                        q.offer(down);
                        visited.add(down);
                    }
                }
            }
            step++;
        }
        return -1;
    }

    /**
     * Flip s[j] up once
     *
     * @param s Given string
     * @param j Current number value
     * @return String
     */
    private String plusOne(String s, int j) {
        char[] ch = s.toCharArray();
        if (ch[j] == '9') {
            ch[j] = '0';
        } else {
            ch[j] += 1;
        }
        return new String(ch);
    }

    /**
     * Move s[i] down once
     *
     * @param s Given string
     * @param j Current number value
     * @return String
     */
    private String minusOne(String s, int j) {
        char[] ch = s.toCharArray();
        if (ch[j] == '0') {
            ch[j] = '9';
        } else {
            ch[j] -= 1;
        }
        return new String(ch);
    }
}