My Java BFS solution


  • 0
    class Solution {
        public int minMutation(String start, String end, String[] bank) {
            if(bank.length == 0) return -1;
            Set<String> set = new HashSet<String>(Arrays.asList(bank));
            if(!set.contains(end)) return -1;
            Queue<String> queue = new LinkedList<String>();
            char [] gene = {'A', 'C', 'G', 'T'};
            int currentLayerNodeNumber = 1;
            int nextLayerNodeNumber = 0;
            int numberOfMutation = 1;
            queue.offer(start);
            while(queue.size() != 0) {
                for(int i = 0; i < currentLayerNodeNumber; i++) {
                    char [] curr = queue.poll().toCharArray();
                    for(int m = 0; m < 8; m++) {
                        for(char temp : gene) {
                            if(temp == curr[m]) continue;
                            char oldChar = curr[m];
                            curr[m] = temp;
                            String mutation = new String(curr);
                            if(mutation.equals(end)) 
                                return numberOfMutation;
                            if(set.contains(mutation)) {
                                queue.offer(mutation);
                                nextLayerNodeNumber++;
                                set.remove(mutation);
                            }
                            curr[m] = oldChar; /* miss this the first time. Need to change char back to original char */
                        }
                    }
                }
                currentLayerNodeNumber = nextLayerNodeNumber;
                nextLayerNodeNumber = 0;
                numberOfMutation++;
            }
            return -1;
        }
    }
    

Log in to reply
 

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