Accepted Java BFS Solution


  • 0
    P
    class Solution {
        public int openLock(String[] deadends, String target) {
            Set<String> used = new HashSet<>();
            Queue<String> q = new LinkedList<>();
            q.offer("0000");
            used.add("0000");
            for(String d : deadends){
                if(d.equals("0000")) // Notice: don't forget to check if deadends contains 0000. 
                                               //If not OJ reports "Wrong Answer" as the picture bellow... 
                                               //Although the test case is nothing about "0000"...
                    return -1;
                used.add(d);
            }
            int ans = 0;
            while(!q.isEmpty()){
                int size = q.size();
                while(size-- > 0){
                    String cur = q.poll();
                    if(cur.equals(target))
                        return ans;
                    String[] newStr = getNext(cur);
                    for(int i = 0; i < 8; i++){
                        if(!used.contains(newStr[i])){
                            used.add(newStr[i]);
                            q.offer(newStr[i]);
                        }
                    }
                }
                ans++;
            }
            return -1;
        }
        
        private String[] getNext(String lock){
            String[] strs = new String[8];
            for(int i = 0; i < 4; i++){
                strs[2 * i] = lock.substring(0, i) + ((lock.charAt(i) - '0' + 1) % 10) + lock.substring(i + 1, 4);
                strs[2 * i + 1] = lock.substring(0, i) + ((lock.charAt(i) - '0' + 9) % 10) + lock.substring(i + 1, 4);
            }
            return strs;
        }
    }
    

    0_1514091613534_1.JPG


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.