leetcode 126. Word Ladder II 单词接龙 II(困难)

2022 年 6 月 08 日
本文字数：2534 字
阅读完需：约 8 分钟

一、题目大意

标签: 搜索

https://leetcode.cn/problems/word-ladder-ii

按字典 wordList 完成从单词 beginWord 到单词 endWord 转化，一个表示此过程的转换序列是形式上像 beginWord -> s1 -> s2 -> ... -> sk 这样的单词序列，并满足：

每对相邻的单词之间仅有单个字母不同。转换过程中的每个单词 si（1 <= i <= k）必须是字典 wordList 中的单词。注意，beginWord 不必是字典 wordList 中的单词。sk == endWord 给你两个单词 beginWord 和 endWord ，以及一个字典 wordList 。请你找出并返回所有从 beginWord 到 endWord 的最短转换序列，如果不存在这样的转换序列，返回一个空列表。每个序列都应该以单词列表 [beginWord, s1, s2, ..., sk] 的形式返回。

示例 1：

输入：beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]输出：[["hit","hot","dot","dog","cog"],["hit","hot","lot","log","cog"]]解释：存在 2 种最短的转换序列："hit" -> "hot" -> "dot" -> "dog" -> "cog""hit" -> "hot" -> "lot" -> "log" -> "cog"

示例 2：

输入：beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log"]输出：[]解释：endWord "cog" 不在字典 wordList 中，所以不存在符合要求的转换序列。

提示：

1 <= beginWord.length <= 5
endWord.length == beginWord.length
1 <= wordList.length <= 5000
wordList[i].length == beginWord.length
beginWord、endWord 和 wordList[i] 由小写英文字母组成
beginWord != endWord
wordList 中的所有单词互不相同

二、解题思路

我们可以把起始字符串、终止字符串、以及单词表里所有的字符串想象成节点。若两个字符串只有一个字符不同，那它们相连。因为题目需要输出个性次数最少的所有修改方式，因此我们可以使用广度优先搜索，求得起始节点到终止节点的最短距离。一个小技巧：我们燕不是直接从起始节点进行广度优先搜索，直到找到终止节点为止，而是从起始节点和终止节点分别进行广度优先搜索，每次只延展当前层节点数最少的那一端，这样我们可以减少搜索的总结点数。举例来说，假设最短距离为 4，如果我们只从一端搜索 4 层，总遍历节点数最多是 1+2+4+8+16=31，如果我们从两端各搜索 2 层，总遍历节点数最多为 2 * (1+2+4)=14。搜索结束后，我们还需要通过回溯法来重建所有可能的路径。

三、解题方法

3.1 Java 实现

public class Solution {    public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {        List<List<String>> ans = new ArrayList<>();        // 优化        Set<String> dict = new HashSet<>(wordList);//        for (String w : wordList) {//            dict.add(w);//        }
        if (!dict.contains(endWord)) {            return ans;        }        dict.remove(beginWord);        dict.remove(endWord);
        Set<String> q1 = new HashSet<>();        q1.add(beginWord);        Set<String> q2 = new HashSet<>();        q2.add(endWord);        Map<String, List<String>> next = new HashMap<>();        boolean reversed = false;        boolean found = false;        while (!q1.isEmpty()) {            Set<String> q = new HashSet<>();            for (String w : q1) {                String s = w;                for (int i = 0; i < s.length(); i++) {                    char[] sArr = s.toCharArray();                    char ch = sArr[i];                    for (int j = 0; j < 26; j++) {                        sArr[i] = (char) (j + 'a');                        s = String.valueOf(sArr);                        if (q2.contains(s)) {                            if (reversed) {                                add(next, s, w);                            } else {                                add(next, w, s);                            }                            found = true;                        }                        if (dict.contains(s)) {                            if (reversed) {                                add(next, s, w);                            } else {                                add(next, w, s);                            }                            q.add(s);                        }                    }                    sArr[i] = ch;                    s = String.valueOf(sArr);                }            }            if (found) {                break;            }            for (String w : q) {                dict.remove(w);            }            if (q.size() <= q2.size()) {                q1 = q;            } else {                reversed = !reversed;                q1 = q2;                q2 = q;            }        }        if (found) {            Deque<String> path = new ArrayDeque<>();            path.add(beginWord);            backTracking(beginWord, endWord, next, path, ans);        }        return ans;    }
    void backTracking(String src, String dst, Map<String, List<String>> next, Deque<String> path, List<List<String>> ans) {        if (src == dst) {            ans.add(new ArrayList<>(path));            return;        }
        for (String s : next.get(src)) {            path.addLast(s);            backTracking(s, dst, next, path, ans);            path.removeLast();        }    }
    private void add(Map<String, List<String>> map, String key, String value) {        if (!map.containsKey(key)) {            map.put(key, new ArrayList<>());        }        map.get(key).add(value);    }}

复制代码

四、总结小记

2022/6/8 这道题烧脑子呀

发布于: 刚刚阅读数: 3

原文链接:【http://xie.infoq.cn/article/b5ba5c09e9f4593fa8492f080】。文章转载请联系作者。

okokabcd

关注

还未添加个人签名 2019.11.15 加入

还未添加个人简介

发布

暂无评论

创作场景