752. Open the Lock

Link

Solution

BFS: 尋找各種可能然後計算最快完成的路徑長度

public int openLock(String[] deadends, String target) {
        String start = "0000";
        int level = 0;
        HashSet<String> visited = new HashSet<>();
        HashSet<String> deadend = new HashSet<>(Arrays.asList(deadends));
        Queue<String> queue = new LinkedList<>();
        queue.add(start);
        visited.add(start);
        while(!queue.isEmpty()){
            
            int size = queue.size();
            for(int k = 0; k < size; k++){
                String cur = queue.poll();
                 if(deadend.contains(cur)) {
                    continue;
                }
                if(cur.equals(target)){
                    return level;
                }
                LinkedList<String> candidates = new LinkedList<>();
                char[] curArray = cur.toCharArray();
                for(int i = 0; i < 4; i++){
                    char c = curArray[i];
                    int num = c - '0';
                    curArray[i] = c == '9' ? '0' : (char)(((num + 1)) + '0');
                    candidates.add(new String(curArray));
                    curArray[i] = c == '0' ? '9' : (char)(((num - 1)) + '0');
                    candidates.add(new String(curArray));
                    curArray[i] = (char) (num + '0');
                }

                for(String candidate : candidates){
                    if(!deadend.contains(candidate) && !visited.contains(candidate))
                    {
                        queue.add(candidate);
                        visited.add(candidate);
                    }
                }
            }
            level++;
        }
        return -1;
    }