Standard Java BFS with queue


  • 0
    H
    class Solution {
        public int openLock(String[] nums, String target) {
            if (target.equals("0000")) return 0;
            
            Set<String> set = new HashSet<>();
            for (String i : nums) set.add(i);
            if (set.contains(target) || set.contains("0000")) return -1;
            
            Queue<String> queue = new LinkedList<>();
            queue.offer("0000");
            
            Set<String> visited = new HashSet<>();
            visited.add("0000");
            
            int level = 0;
            while (!queue.isEmpty()) {
                int size = queue.size();
                level++;
                for (int i = 0; i < size; i++) {
                    String cur = queue.poll();
                    for (int j = 0; j < 4; j++) {
                        char one = (char)(cur.charAt(j) + 1), two = (char)(cur.charAt(j) - 1);
                        if (cur.charAt(j) == '0') two = '9';
                        if (cur.charAt(j) == '9') one = '0';
                        
                        String a = cur.substring(0, j) + one + cur.substring(j + 1);
                        String b = cur.substring(0, j) + two + cur.substring(j + 1);
                        
                        if (a.equals(target) || b.equals(target)) return level;
                        if (!visited.contains(a) && !set.contains(a)) {
                            visited.add(a);
                            queue.offer(a);
                        }
                        if (!visited.contains(b) && !set.contains(b)) {
                            visited.add(b);
                            queue.offer(b);
                        }
                    }
                }
            }
            return -1;
        }
    }
    

Log in to reply
 

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