Java BFS 2ms


  • 0
    A
    public class Solution {
        public int minMutation(String start, String end, String[] bank)
        {
            if(start.equalsIgnoreCase(end))
                return 0;
            
            char [] vocab = {'A','C','G','T'}; 
            Set<String> pool = new HashSet<String>();
            
            for(String b : bank)
                pool.add(b);
            
            if(!pool.contains(end))
            	return -1;
            
            int result=0;
            Deque<String> nextMutations = new ArrayDeque<String>();
                nextMutations.offerLast(start);
                
            while(!nextMutations.isEmpty())
            {
                int qsize = nextMutations.size();
                
                for(int x=0; x<qsize; x++)
                {
                    String current = nextMutations.pollFirst();
                   
                    if(current.equalsIgnoreCase(end))
                        return result;
                    
                    pool.remove(current);
                    
                    StringBuilder c = new StringBuilder(current);
                    
                    for(char g : vocab)
                    {
                        for(int i=0; i<c.length(); i++)
                        {
                        	StringBuilder oldc = new StringBuilder(c);
                            
                            if(c.charAt(i)!=g)
                            {
    	                        c.setCharAt(i,g);
    	                        if(pool.contains(c.toString()))
    	                           nextMutations.offerLast(c.toString());
    	                    }
                            
                            c=oldc;
                        }
                    }
                }
                
                result++;
            }
            
            return -1;
        }
    }
    

Log in to reply
 

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