Java BFS Straightforward Solution


  • 0
    public class Solution {
        public int minMutation(String start, String end, String[] bank) {
            Set<String> bankset = new HashSet<>();
            Queue<String> tmp = new LinkedList<>();
            Queue<Integer> level = new LinkedList<>();
            
            for(String s: bank){
                bankset.add(s);            
            }
            if(!bankset.contains(end))
                return -1;
            tmp.add(start); level.add(1);
            
            while(!tmp.isEmpty()){
                String s = tmp.poll();
                int l = level.poll();
                for(String b: bankset){
                    if(oneMutation(b, s)){
                        if(b.equals(end))
                           return l;
                        else{
                           tmp.add(b);
                           level.add(l + 1);
                        }
                    }
                }
            }
            
            return -1;
        }
        
        boolean oneMutation(String a, String b){
            if(a.length() != b.length())
                return false;
            int difference = 0;
            for(int i = 0; i < a.length(); i++){
                if(a.charAt(i) != b.charAt(i))
                    difference ++;
            }
            return difference == 1;
        }
    }
    

Log in to reply
 

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