Java solution


  • 0
    N
    import java.util.ArrayList;
    
    class Solution {        
        public int minMutation(String start, String end, String[] bank) {        
            if(start.length() != end.length()){
                return -1;
            }
            ArrayList<String> list = new ArrayList<String>(Arrays.asList(bank));
            char[] chars = {'A', 'C', 'G', 'T'};
            int res = getPossibilities(start, end, list, chars, 0);          
            System.out.println(res);        
            return res;        
        }
        
        
        public static int getPossibilities(String start, String end, ArrayList<String> bank, char[] chars, int count){
            ArrayList<String> pos = new ArrayList<String>();
            //get all valid possibilities that bank contains 
            for(int i = 0; i < start.length(); i++){
                for(char c : chars){
                    String newWord = start.substring(0, i) + c;
                    if(i+1 < end.length()){
                        newWord += start.substring(i+1);
                    }
                    if(bank.contains(newWord)){
                        pos.add(newWord);
                        bank.remove(newWord);
                    } 
                }
            }
            //if find possibilities add 1 to count
            if(!pos.isEmpty()){
                count++;
            }
            //for each possibility, get more possibilities or return the count if we have found the correct one            
            for(String p : pos){
                //if one of the possibilities equals end, return count
                if(p.equals(end)){
                    return count;
                }
                //for each possibility, find more possibilities
                int pCount = getPossibilities(p, end, bank, chars, count);
                if(pCount >= 0){
                    return pCount;
                }
            }        
           //if no possibilities returned a count >= 0, return -1
           return -1;
        }    
    }
    

Log in to reply
 

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