class Solution {
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        Set<String> set = new HashSet<>(wordList);
        if(!set.contains(endWord)) return 0;
        
        Queue<String> queue = new LinkedList<>();
        Set<String> visited = new HashSet<>();
        queue.offer(beginWord);
        int step = 0;
        while(!queue.isEmpty()) {
            int size = queue.size();
            for(int i = 0; i < size; i++) {
                String str = queue.poll();
                if(!set.contains(str) || visited.contains(str)) continue;
                if(str.equals(endWord)) return step;
                visited.add(str);
                for(int j = 0; j < str.length(); j++) {
                    for (int k = 0; k < 26; k++) {
                        queue.offer(str.substring(0, j) + String.valueOf('a' + k) + str.substring(j + 1));
                    }
                }
            }
            step++;
        }
        return -1;
    }
}