打开转盘锁

你有一个带有四个圆形拨轮的转盘锁。每个拨轮都有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

解释：

无法旋转到目标数字且不被锁定。

示例 4:

输入: deadends = ["0000"], target = "8888"

输出：-1

提示：

死亡列表 deadends 的长度范围为 [1, 500]。

目标数字 target 不会在 deadends 之中。

每个 deadends 和 target 中的字符串的数字会在 10,000 个可能的情况 '0000' 到 '9999' 中产生。

思路1 广度优先搜索

//用两个队列实现宽度优先遍历。队列queue1里存的是需要转动n次达到的顶点，
// queue2是和queue1里的顶点相连同时还没有遍历到的顶点。
// 当queue1的里顶点都删掉之后，接着遍历需要转动n+1次到达的顶点，
// 也就是queue2里的顶点，此时变量steps加1。
public static int openLock(String[] deadends, String target) {
    if(target==null || target.length()==0){
        return -1;
    }
    String start="0000";
    Set<String> deads=new HashSet<>(Arrays.asList(deadends));
    Set<String> visited = new HashSet<>();
    if(deads.contains(target) || deads.contains(start)){
        return -1;
    }
    Queue<String> queue1 = new LinkedList<>();
    Queue<String> queue2 = new LinkedList<>();
    int steps = 0;
    queue1.offer(start);

    while(!queue1.isEmpty()){
        String cur = queue1.poll();
        if (cur.equals(target)) {
            return steps;
        }
        List<String> nexts = getNexts(cur);
        for (String next : nexts) {
            if (!deads.contains(next) && !visited.contains(next)) {
                visited.add(next);
                queue2.offer(next);
            }
        }
        if (queue1.isEmpty()) {
            steps++;
            queue1 = queue2;
            queue2 = new LinkedList<>();
        }
    }
    return -1;
}

//它的作用是根据密码锁的转动规则得到与某一状态相连的8个状态：
private static List<String> getNexts(String cur) {
    List<String> nexts = new LinkedList<>();
    for (int i = 0; i < cur.length(); ++i) {
        char ch = cur.charAt(i);

        char newCh = ch == '0' ? '9' : (char)(ch - 1);
        StringBuilder builder = new StringBuilder(cur);
        builder.setCharAt(i, newCh);
        nexts.add(builder.toString());

        newCh = ch == '9' ? '0' : (char)(ch + 1);
        builder = new StringBuilder(cur);
        builder.setCharAt(i, newCh);
        nexts.add(builder.toString());
    }

    return nexts;
}

解法二：双向广度优先搜索

这个问题是单个源点（"0000"）单个目标（输入的target）的广度优先搜索。我们可以想象当我们到达目标节点的时候，我们同时还遍历了求解树中位于同一层的其他节点。尽管在那一层中我们只需要遍历一个节点，我们却实际上遍历很多不必要的节点，因此单向搜索是存在优化空间的。

我们可以把单项搜索改为双向搜索，也就是既从源点出发向着目标搜索，也从目标出发向着源点搜索。如果两个方向搜索最终能够在中间某个位置相遇，那么表明存在从源点到目标的路径。

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

    if (target.equals(init)) {
        return 0;
    }

    Set<String> set1 = new HashSet<>();
    set1.add(init);
    Set<String> set2 = new HashSet<>();
    set2.add(target);

    int steps = 0;
    while (!set1.isEmpty() && !set2.isEmpty()) {
        if (set1.size() > set2.size()) {
            Set<String> temp = set1;
            set1 = set2;
            set2 = temp;
        }

        Set<String> set3 = new HashSet<>();
        for (String cur : set1) {
            for (String next : getNexts(cur)) {
                if (set2.contains(next)) {
                    return steps + 1;
                }

                if (!dead.contains(next) && !visited.contains(next)) {
                    visited.add(next);
                    set3.add(next);
                }
            }
        }

        steps++;
        set1 = set3;
    }
    return -1;
}

private List<String> getNexts(String cur) {
    List<String> nexts = new LinkedList<>();
    for (int i = 0; i < cur.length(); ++i) {
        char ch = cur.charAt(i);

        char newCh = ch == '0' ? '9' : (char)(ch - 1);
        StringBuilder builder = new StringBuilder(cur);
        builder.setCharAt(i, newCh);
        nexts.add(builder.toString());

        newCh = ch == '9' ? '0' : (char)(ch + 1);
        builder = new StringBuilder(cur);
        builder.setCharAt(i, newCh);
        nexts.add(builder.toString());
    }

    return nexts;
}

其中一个改动是保存节点的数据结构由队列Queue改成了集合HashSet。这是由于我们需要判断我们某一方向搜索的节点是不是位于另一个方向搜索的集合之中（也就是判断两个方向的搜索是否相遇）。HashSet能够更高效地完成这一要求。另外，我们只要做到遍历求解树的一层之后遍历下一层。同一层的遍历顺序并不重要，因此广度优先搜索算法本身也不是一定要用先进先出的队列实现。

我们一共用了三个集合。集合set1和set2保存两个方向当前遍历层的节点。我们总是优先遍历set1和set2中节点数目较少的那个方向的节点（通过交换set1和set2确保set1中的节点数目总是小于set2的）。集合set3保存的set1的节点的下一层节点。

上述代码改动虽然很小，但性能优化效果却很明显。LeetCode的测试数据表明优化之后的运行时间只有优化之前的运行时间的四分之一到三分之一。