Simple 2ms BFS Java solution


  • 0
    public int minMutation(String start, String end, String[] bank) {
        boolean[] visited = new boolean[bank.length];
        Queue<String> queue = new LinkedList<>();
        queue.add(start);
        int size = 1, res = 1;
        while(!queue.isEmpty()){
            String temp = queue.poll();
            for(int i = 0; i < bank.length; i++){
                if (oneDistance(temp, bank[i]) && visited[i] == false){
                    if (bank[i].equals(end)) return res;
                    queue.add(bank[i]);
                    visited[i] = true;
                }
            }
            size--;
            if (size == 0){
                res++;
                size = queue.size();
            }
        }
        return -1;
    }
    private boolean oneDistance(String str1, String str2) {
        int count = 0;
        for (int i = 0; i < str1.length(); i++){
            if (str1.charAt(i) != str2.charAt(i)) count++;
            if (count > 1) return false;
        }
        return count == 1;
    }

Log in to reply
 

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