Java DFS 2 ms


  • 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;
            
            Map<String,Integer> minMutationsPerString = new HashMap<String,Integer>();
            minMutationsPerString.put(end,0);
            
            return minMutation(start,minMutationsPerString,pool,vocab);
        }
        
        public int minMutation(String current, Map<String,Integer> minMutationsPerString, Set<String> pool, char[] vocab)
        {
            if(minMutationsPerString.containsKey(current))
                return minMutationsPerString.get(current);
                
            int result=-1;
            
            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()))
    	                       {
    	                           int r = 1 + minMutation(c.toString(),minMutationsPerString,pool,vocab);
    	                           
    	                           if(r>0)
    	                               if(result==-1) 
    	                            	   result = r ;
    	                               else 
    	                            	   result = Math.min(result,r);
    	                       }
                                
                            }
                            
                            c=oldc;
                        }
                    }
                    
            minMutationsPerString.put(current,result);
            return result;
        }
    }
    

Log in to reply
 

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