752. 打开转盘锁 (opens new window)

1.BFS广搜

思路：本题使用广搜，具体来说，将下一次拨动可能出现的密码锁字符串加入队列当中，加入前需要判断该字符串①是否是死锁字符串。②是否是前面出现过的字符串。

为什么不能使用深搜？

使用深搜关键在缓存cache如何进行设置。

• key-value存放<当前字符串，轮次>，轮次大于缓存次数的退出循环。这种方法复杂度会很高，最坏情况下会搜索出拨动40次的1000种结果。
• 存放字符串+当前轮次，那么对于000>010>000这种情况，会出现缓存溢出。

故最优解是按照当前轮次的所有可能结果来进行BFS搜索。

class Solution {
    public int openLock(String[] deadends, String target) {
        Set<String> set = new HashSet<>();
        for (int i = 0; i < deadends.length; i++) {
            set.add(deadends[i]);
        }
        Set<String> cache = new HashSet<>();
        Deque<String> queue = new LinkedList<>();
        cache.add("0000");
        queue.offerLast("00000");
        int ans = -1;
        //广搜
        while (!queue.isEmpty()) {
            String s = queue.pollFirst();
            Integer count = Integer.valueOf(s.substring(4));
            String str = s.substring(0, 4);
            if(set.contains(str)) continue;
            if (str.equals(target)) {
                ans = count;
                break;
            }
            for (int i = 0; i < 4; i++) {
                Integer integer = Integer.valueOf(str.substring(i, i + 1));
                int pre = integer == 0 ? 9 : integer - 1;
                int next = integer == 9 ? 0 : integer + 1;
                String preStr = str.substring(0, i) + String.valueOf(pre) + str.substring(i + 1, 4);
                String nextStr = str.substring(0, i) + String.valueOf(next) + str.substring(i + 1, 4);
                if (!cache.contains(preStr)&&!set.contains(preStr)) {
                    cache.add(preStr);
                    queue.offerLast(preStr + String.valueOf(count+1));
                }
                if (!cache.contains(nextStr)&&!set.contains(nextStr)) {
                    cache.add(nextStr);
                    queue.offerLast(nextStr + String.valueOf(count+1));
                }

            }
        }
        return ans;
    }
}