Java Easy BFS Solution 2ms


  • 1
    G
    public class Solution {
        public int minMutation(String start, String end, String[] bank) {
            Set<String> set=new HashSet<String>();
            char[] chars={'A','C','G','T'};
            for(String b:bank)set.add(b);
            
            if(!set.contains(end))return -1;
            Queue<Container> q=new LinkedList<Container>();
            q.add(new Container(start,0));
            
            while(!q.isEmpty()) {
                Container con=q.remove();
                char[] str=con.word.toCharArray();
                
                for(int i=0;i<str.length;i++) {
                    char tmpChar=str[i];
                    for(char c:chars) {
                        if(c==str[i]) continue;
                        str[i]=c;
                        String tmpStr=new String(str);
                        if(tmpStr.equals(end))
                            return con.steps+1;
                        if(set.contains(tmpStr))
                            q.add(new Container(tmpStr,con.steps+1));
                        
                    }
                    str[i]=tmpChar;
                }
            }
            return -1;
        }
    }
    
    class Container {
        String word;
        int steps;
        public Container(String word,int steps) {
            this.word=word;
            this.steps=steps;
        }
    }
    

Log in to reply
 

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