Java BFS similar to WordLadder


  • 0
        public int minMutation(String start, String end, String[] bank) {
            if (bank == null || bank.length == 0) return -1;
            if (start.equals(end)) return 0;
            Set<String> bankset = new HashSet<>();
            for (String s : bank) bankset.add(s);
            if (!bankset.contains(end)) return -1; // end work must in the bank according to testcases
            
            char[] chars = new char[]{'A', 'C', 'G', 'T'};
            int step = 0;
            // Set<String> visited = new HashSet<>();
            Queue<String> queue = new LinkedList<>();
            queue.offer(start);
            // visited.add(start);
            
            while (!queue.isEmpty()) {
                int size = queue.size();
                for (int i = 0; i < size; i++) {
                    String curr = queue.poll();
                    if (curr.equals(end)) return step;
                    
                    char[] currArr = curr.toCharArray();
                    for (int j = 0; j < currArr.length; j++) {
                        char original = currArr[j];
                        for (char c : chars) {
                            currArr[j] = c;
                            String temp = new String(currArr);
                            if (temp.equals(end)) return step + 1;
                            if (bankset.contains(temp)) {
                                bankset.remove(temp);
                                queue.offer(temp);
                            }
                        }
                        currArr[j] = original; 
                    }
                }
                step += 1;
            }
            return -1;
        }
    

Log in to reply
 

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