752. Open the Lock

class Solution {
    public int openLock(String[] deadends, String target) {
        Set<String> deadEndSet = new HashSet<>(Arrays.asList(deadends));
        Set<String> visitedWordSet = new HashSet<>(); // 防止重复访问

        Set<String> q1 = new HashSet<>();
        q1.add("0000");
        Set<String> q2 = new HashSet<>();
        q2.add(target);

        int count = 0;

        while (!q1.isEmpty() && !q2.isEmpty()) {
            Set<String> nextLayerWords = new HashSet<>();

            for (String word : q1) {
                if (deadEndSet.contains(word)) {
                    continue;
                }
                if (q2.contains(word)) { // 注意此处是第二个队列包含 word, 说明寻找到路径
                    return count;
                }
                visitedWordSet.add(word);
                for (int i = 0; i < 4; i++) {
                    String upWord = moveUp(word, i);
                    if (!visitedWordSet.contains(upWord)) {
                        nextLayerWords.add(upWord);
                    }
                    String downWord = moveDown(word, i);
                    if (!visitedWordSet.contains(downWord)) {
                        nextLayerWords.add(downWord);
                    }
                }
            }

            q1 = q2; // q1 已经遍历完成，下次遍历 q2
            q2 = nextLayerWords;
            count++;
        }

        return -1;
    }

    private String moveUp(String word, int i) {
        char[] chars = word.toCharArray();
        chars[i] = chars[i] == '9' ? '0' : (char) (chars[i] + 1);
        return new String(chars);
    }

    private String moveDown(String word, int i) {
        char[] chars = word.toCharArray();
        chars[i] = chars[i] == '0' ? '9' : (char) (chars[i] - 1);
        return new String(chars);
    }
}

双向 BFS 实现，节省空间。

References

752. Open the Lock
剑指 Offer II 109. 开密码锁