LeetCode127-单词接龙

题目链接

英文链接：https://leetcode.com/problems/word-ladder/

中文链接：https://leetcode-cn.com/problems/word-ladder/

题目详述

给定两个单词（beginWord 和 endWord）和一个字典，找到从 beginWord 到 endWord 的最短转换序列的长度。转换需遵循如下规则：

1. 每次转换只能改变一个字母。
2. 转换过程中的中间单词必须是字典中的单词。

说明:

• 如果不存在这样的转换序列，返回 0。
• 所有单词具有相同的长度。
• 所有单词只由小写字母组成。
• 字典中不存在重复的单词。
• 你可以假设 beginWord 和 endWord 是非空的，且二者不相同。

示例 1:

输入:
beginWord = "hit",
endWord = "cog",
wordList = ["hot","dot","dog","lot","log","cog"]

输出: 5

解释: 一个最短转换序列是 "hit" -> "hot" -> "dot" -> "dog" -> "cog",
     返回它的长度 5。

示例 2:

输入:
beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log"]

输出: 0

解释: endWord "cog" 不在字典中，所以无法进行转换。

题目详解

方法一：BFS。

可以将每个单词看成图中的一个结点，如果两个单词之间可以互相转化，那么这两个单词所在的结点就有一条无向边。问题就转为从起点到终点的的最短路径。由于边权都相等，可以用 BFS 求最短路。

时间复杂度分析：

• BFS 过程中每个点会遍历一次，每个点需要枚举所有结点，判断是否存在边，需要判断 O(n^2) 次。
• 假设单词长度为 L，每次判断需要 O(L) 次。
• 总的时间复杂度为 O(n^2 * L)。

public class LeetCode_00127 {

    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        Queue<String> queue = new LinkedList<>();
        Set<String> set = new HashSet<>();
        queue.offer(beginWord);
        set.add(beginWord);
        int level = 1;
        while (!queue.isEmpty()) {
            ++level;
            int size = queue.size();
            while (size-- != 0) {
                String word = queue.poll();
                for (String w : wordList) {
                    if (set.contains(w)) {
                        continue;
                    }
                    if (match(word, w)) {
                        if (w.equals(endWord)) {
                            return level;
                        }
                        queue.offer(w);
                        set.add(w);
                    }
                }
            }
        }
        return 0;
    }

    private boolean match(String word, String w) {
        boolean changedOnce = false;
        for (int i = 0; i < word.length(); ++i) {
            if (word.charAt(i) != w.charAt(i)) {
                if (changedOnce) {
                    return false;
                } else {
                    changedOnce = true;
                }
            }
        }
        return true;
    }
}

方法二：双向 BFS（Bidirectional BFS）。

双向 BFS 就是从头尾两个方向进行 BFS。当头尾两个队列重叠时，说明可以从起始点可以到达目标点。这种方法，在搜索某个特定目标时非常有用。

• 构建头尾队列。
• 优先扩展队列大小较小的，保持头队列为包含元素较少的队列。即头队列大小大于尾队列时，交换头尾队列。
• 从头队列向尾队列的方向搜索直至二者存在重叠的地方。
• 在搜索的过程，构建下一次的头队列，并在一次扩展结束时更新头队列。
• 另外，通常可以加上访问标志来进行剪枝。

时间复杂度分析：

• 在下面的实现中，改为循环改变一个字母，1 个长度为 L 的字符串的计算量为 26 L，n 个字符串就是 26 L * n。
• 每次在哈希表中判断修改后的单词是否存在还需要 O(L) 的计算量，总时间复杂度为 O(26 L ^ 2 n) = O(L^2 * n)。

public class LeetCode_00127 {

    // 双向 BFS
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        // 构建一个包含所有单词的字典
        Set<String> dict = new HashSet<>(wordList);
        // 字典中不包含 endWord，不可能经过转换得到 endWord
        if (!dict.contains(endWord)) {
            return 0;
        }
        // 构建头尾队列
        Set<String> head = new HashSet<>();
        Set<String> tail = new HashSet<>();
        head.add(beginWord);
        tail.add(endWord);
        // 注意长度是结点数，而不是边数
        int level = 1;
        while (!head.isEmpty() && !tail.isEmpty()) {
            ++level;
            // 确保头集合较小，保持平衡
            if (head.size() > tail.size()) {
                Set tmp = head;
                head = tail;
                tail = tmp;
            }
            // 构建下一次迭代的头队列
            Set<String> newHead = new HashSet<>();
            for (String word : head) {
                char[] cs = word.toCharArray();
                for (int i = 0; i < cs.length; ++i) {
                    char ch = cs[i];
                    for (char j = 'a'; j <= 'z'; ++j) {
                        // 变动一个字符得到新字符串
                        cs[i] = j;
                        String s = new String(cs);
                        // 到达目标点
                        if (tail.contains(s)) {
                            return level;
                        }
                        // 剪枝。在字典中存在才添加到新的头队列中，并更新字典
                        if (dict.contains(s)) {
                            dict.remove(s);
                            newHead.add(s);
                        }
                    }
                    // 还原
                    cs[i] = ch;
                }
            }
            // 得到新的头队列
            head = newHead;
        }
        return 0;
    }
}