一、题目

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

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

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

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

点击查看原题
难度级别： 中等（感觉有点困难题的意思了）

二、思路

1）BFS

首先说明为什么DFS不能使用，因为DFS会反复在同一步长范围内搜索，无法正确返回最短步长
使用BFS，可以优先记录走过的步长的字符串。在遍历的时候，令visited为访问过字符串的集合，令deadset为死锁集合，只有两个集合都没有存在的字符串，才能进行下一步访问。

三、代码

1）BFS

class Solution {
    public int openLock(String[] deadends, String target) {
        Set<String> deadset = new HashSet();
        Set<String> visited = new HashSet();
        for (String s : deadends) {
            deadset.add(s);
        }
        if ("0000".equals(target)) {
            return 0;
        }
        if (deadset.contains("0000")) { // 开局死锁
            return -1;
        }
        int step = 1;
        Queue<String> q = new LinkedList();
        q.offer("0000");
        while (!q.isEmpty()) {
            int len = q.size();
            while (len-- > 0) {
                String s = q.poll();
                List<String> nextStrings = getNextStep(s);    // 根据s获取下一步所有有可能字符串
                for (String nextString : nextStrings) {
                    // 只有没有访问过和不死锁的字符串，才能下一步遍历
                    if (deadset.contains(nextString) || visited.contains(nextString)) {
                        continue;
                    }
                    // 在此处就确定是否为目标字符串，可以提高程序速度
                    if (nextString.equals(target)) {
                        return step;
                    }
                    q.offer(nextString);
                    // 一定要在此添加被访问过的字符串集合，否则会成为dfs，血的教训
                    visited.add(nextString);
                }
            }
            step++;
        }
        return -1;
    }
    private List<String> getNextStep(String s) {
        List<String> ret = new ArrayList<String>();
        char[] array = s.toCharArray();
        for (int i = 0; i < 4; ++i) {
            char num = array[i];
            array[i] = (num == '9') ? '0' : (char)(num + 1);
            ret.add(new String(array));
            array[i] = (num == '0') ? '9' : (char)(num - 1);
            ret.add(new String(array));
            array[i] = num;
        }
        return ret;
    }
}

b是数字进制10，d是数字位数4，n是数组长度，时间复杂度为O(``b^d*``d^2+n*d``)，空间复杂度为O(``b^d*d``+n``)