当前位置 : 主页 > 编程语言 > 其它开发 >

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

来源:互联网 收集:自由互联 发布时间:2022-06-09
我们可以把起始字符串、终止字符串、以及单词表里所有的字符串想象成节点。若两个字符串只有一个字符不同,那它们相连。因为题目需要输出个性次数最少的所有修改方式,因此我
我们可以把起始字符串、终止字符串、以及单词表里所有的字符串想象成节点。若两个字符串只有一个字符不同,那它们相连。因为题目需要输出个性次数最少的所有修改方式,因此我们可以使用广度优先搜索,求得起始节点到终止节点的最短距离。 一、题目大意

标签: 搜索

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 这道题烧脑子呀
上一篇:[UG 二次开发 PYTHON] 添加螺纹规格
下一篇:没有了
网友评论