Word Ladder

1public int ladderLength(String beginWord, String endWord, List<String> wordList) {
2    Set<String> dictSet = new HashSet<>(wordList);
3    if (!dictSet.contains(endWord)) {
4        return 0;
5    }
6
7    Queue<String> queue = new LinkedList<>();
8    Set<String> visited = new HashSet<>();
9    queue.offer(beginWord);
10    visited.add(beginWord);
11    int steps = 1;
12
13    while (!queue.isEmpty()) {
14        int levelSize = queue.size();
15
16        for (int i = 0; i < levelSize; i++) {
17            String current = queue.poll();
18            if (current.equals(endWord)) {
19                return steps;
20            }
21
22            // Get neighbors (differ by 1 letter)
23            char[] chars = current.toCharArray();
24            for (int j = 0; j < chars.length; j++) {
25                char original = chars[j];
26                for (char c = 'a'; c <= 'z'; c++) {
27                    chars[j] = c;
28                    String neighbor = new String(chars);
29                    if (dictSet.contains(neighbor) && !visited.contains(neighbor)) {
30                        visited.add(neighbor);
31                        queue.offer(neighbor);
32                    }
33                }
34                chars[j] = original;
35            }
36        }
37
38        steps++;
39    }
40
41    return 0;
42}