127. Word Ladder

BFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
class Solution {
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        Set<String> wordSet = new HashSet<>(wordList);
        if (!wordSet.contains(endWord)) {
            return 0;
        }

        int length = 1;
        Queue<String> queue = new LinkedList<>();
        queue.add(beginWord);

        while (!queue.isEmpty()) {
            for (int i = queue.size(); i > 0; i--) { // 注意 i 起始是 queue.size() 的话 i 需要大于 0
                String word = queue.poll();
                if (endWord.equals(word)) {
                    return length;
                }

                char[] chars = word.toCharArray();
                for (int j = 0; j < chars.length; j++) {
                    char sourceChar = chars[j];
                    for (char c = 'a'; c <= 'z'; c++) {
                        if (c == sourceChar) {
                            continue;
                        }

                        chars[j] = c;
                        String nextWord = new String(chars);
                        if (wordSet.contains(nextWord)) {
                            queue.offer(nextWord);
                            wordSet.remove(nextWord);
                        }
                    }
                    chars[j] = sourceChar;
                }
            }

            length++;
        }

        return 0;
    }
}

BFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
class Solution {
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        Set<String> wordSet = new HashSet<>(wordList);
        if (!wordSet.contains(endWord)) {
            return 0;
        }

        Queue<String> queueA = new LinkedList<>();
        queueA.add(beginWord);
        Queue<String> queueB = new LinkedList<>();
        queueB.add(endWord);

        Map<String, Integer> wordToEdgeCountMapA = new HashMap<>();
        wordToEdgeCountMapA.put(beginWord, 0);
        Map<String, Integer> wordToEdgeCountMapB = new HashMap<>();
        wordToEdgeCountMapB.put(endWord, 0);

        while (!queueA.isEmpty() && !queueB.isEmpty()) {
            int edgeCount;

            // 注意此处必须是 <= 而不能是 <, 因为 wordList 不包含 beginWord, 如："hog", "cog", ["cog"], 如果从 endWord 开始搜索则无法到达 hog, 导致答案错误
            if (queueA.size() <= queueB.size()) {
                edgeCount = tryConnect(wordSet, queueA, wordToEdgeCountMapA, wordToEdgeCountMapB);
            } else {
                edgeCount = tryConnect(wordSet, queueB, wordToEdgeCountMapB, wordToEdgeCountMapA);
            }

            if (edgeCount != -1) {
                return edgeCount + 1; // 注意题目要求返回单词数量，即图中节点数量
            }
        }

        return 0;
    }

    private int tryConnect(Set<String> wordSet, Queue<String> queue, Map<String, Integer> wordToEdgeCountMap, Map<String, Integer> otherWordToEdgeCountMap) {
        for (int i = queue.size(); i > 0; i--) {
            String word = queue.poll();
            int edgeCount = wordToEdgeCountMap.get(word);

            char[] chars = word.toCharArray();
            for (int j = 0; j < chars.length; j++) {
                char sourceChar = chars[j];
                for (char c = 'a'; c <= 'z'; c++) {
                    if (c == sourceChar) {
                        continue;
                    }

                    chars[j] = c;
                    String nextWord = new String(chars);
                    if (wordToEdgeCountMap.containsKey(nextWord) && wordToEdgeCountMap.get(nextWord) <= edgeCount + 1) {
                        continue;
                    }
                    if (wordSet.contains(nextWord)) {
                        if (otherWordToEdgeCountMap.containsKey(nextWord)) {
                            return edgeCount + 1 + otherWordToEdgeCountMap.get(nextWord);
                        }
                        queue.offer(nextWord);
                        wordToEdgeCountMap.put(nextWord, edgeCount + 1);
                    }
                }
                chars[j] = sourceChar;
            }
        }

        return -1;
    }
}

References

127. Word Ladder
剑指 Offer II 108. 单词演变