Java Solution + Using BFS to calculate shortest path


  • 0
    R

    Use BFS to calculate shortest Path

    public int minMutation(String start, String end, String[] bank) {
            HashSet<String> set = new HashSet<>(Arrays.asList(bank));
            if(!set.contains(end))
                return -1;
            Queue<String> curr = new LinkedList<>();
            Queue<String> next = new LinkedList<>();
            curr.offer(start);
            int level = 0;
            
            char[] geneChars = {'A', 'C', 'G', 'T'};
            
            while(!curr.isEmpty()) {
                String temp = curr.poll();  
                for(int i = 0; i < temp.length(); i++) {
                    for(char c : geneChars) {
                        if(c == temp.charAt(i))
                            continue;
                        String newGene = temp.substring(0, i) + c + temp.substring(i + 1);
                        if(newGene.equals(end) )
                            return level + 1;
                            
                        if(set.contains(newGene)) {
                            next.offer(newGene);
                            set.remove(newGene);
                        }
                    }
                }
                
                if(curr.isEmpty()) {
                    level++;
                    Queue swap = curr;
                    curr = next;
                    next = swap;
                }
            }
            return -1;
        }
    

Log in to reply
 

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