# 0752. Open the Lock
###### tags: `Leetcode` `FaceBook` `Medium` `BFS` `Bidirectional BFS`
Link: https://leetcode.com/problems/open-the-lock/
## 思路
bfs层序遍历找最短路径，最多有10000个可能的排列组合
这里可以把visited和deadStr合并

**Bidirectional BFS** [介绍] (https://www.geeksforgeeks.org/bidirectional-search/)
相比于普通bfs，节省很多时间
用directional bfs的条件:
- Both initial and goal states are unique and completely defined.
- The branching factor is exactly the same in both directions.

其实就是一次从root开始搜，然后把下一层的node加进一个temp list里面，然后把begin = end，end = temp做交换，这样下一次就是从target开始搜，如果搜到的某个string，在另一个set里面，就说明找到了
这里要注意的是bidirectional bfs不能在找到next，并且发现next没有被visited之后，就加进visited里面，因为这样另外一端永远也找不到这个字串

可以进一步优化: 每次建完temp之后，比较temp的大小和end的大小，哪个小，下次就用哪个搜索，具体解法可以看[这里](https://leetcode.com/problems/open-the-lock/discuss/110237/Regular-java-BFS-solution-and-2-end-BFS-solution-with-improvement)

## Code
BFS

class Solution {
    public int openLock(String[] deadends, String target) {
        Set<String> deadStr = new HashSet<>();
        for(int i = 0;i < deadends.length;i++){
            deadStr.add(deadends[i]);
        }
        Queue<String> q = new LinkedList<>();
        if(deadStr.contains("0000")) return -1;
        q.add("0000");
        Set<String> visited = new HashSet<>();
        int depth = 0;
        while(!q.isEmpty()){
            int size = q.size();
            for(int i = 0;i < size;i++){
                String curr = q.poll();
                if(curr.equals(target)) return depth;
                for(String next:getNext(curr)){
                    if(!visited.contains(next)&&!deadStr.contains(next)){
                        visited.add(next);
                        q.add(next);
                    }
                }   
            }
            depth++;
        }
        return -1;
    }
    private List<String> getNext(String curr){
        char[] charArray = curr.toCharArray();
        List<String> ans = new ArrayList<>();
        for(int i = 0;i < charArray.length;i++){
            char c = charArray[i];
            char newChar = c+1<='9'?(char)(c+1):'0';
            charArray[i] = newChar;
            ans.add(new String(charArray));
            
            newChar = c-1>='0'?(char)(c-1):'9';
            charArray[i] = newChar;
            ans.add(new String(charArray));
            
            charArray[i] = c;
        }
        return ans;
    }
}

Bidirectional BFS

class Solution {
    public int openLock(String[] deadends, String target) {
        Set<String> deadStr = new HashSet<>();
        for(int i = 0;i < deadends.length;i++){
            deadStr.add(deadends[i]);
        }
        Set<String> begin = new HashSet<>();
        Set<String> end = new HashSet<>();
        if(deadStr.contains("0000")) return -1;
        begin.add("0000");
        end.add(target);
        int depth = 0;
        while(!begin.isEmpty() && !end.isEmpty()){
            Set<String> temp = new HashSet<>();
            for(String s:begin){
                if(end.contains(s)) return depth;
                deadStr.add(s);
                for(String next:getNext(s)){
                    if(!deadStr.contains(next)){
                        temp.add(next);
                    }
                }
            }
            depth++;
            begin = end;
            end = temp;
        }
        return -1;
    }
    private List<String> getNext(String curr){
        char[] charArray = curr.toCharArray();
        List<String> ans = new ArrayList<>();
        for(int i = 0;i < charArray.length;i++){
            char c = charArray[i];
            char newChar = c+1<='9'?(char)(c+1):'0';
            charArray[i] = newChar;
            ans.add(new String(charArray));
            
            newChar = c-1>='0'?(char)(c-1):'9';
            charArray[i] = newChar;
            ans.add(new String(charArray));
            
            charArray[i] = c;
        }
        return ans;
    }
}