126. Word Ladder II

 

Given two words ( beginWord  and  endWord ), and a dictionary’s word list, find all shortest transformation sequence(s) from  beginWord  to  endWord , such that:

  1. Only one letter can be changed at a time
  2. Each transformed word must exist in the word list. Note that  beginWord  is  not  a transformed word.

Note:

  • Return an empty list if there is no such transformation sequence.
  • All words have the same length.
  • All words contain only lowercase alphabetic characters.
  • You may assume no duplicates in the word list.
  • You may assume  beginWord  and  endWord  are non-empty and are not the same.

Example 1:

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

Output:
[
  ["hit","hot","dot","dog","cog"],
  ["hit","hot","lot","log","cog"]
]

Example 2:

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

Output: []

Explanation: The endWord "cog" is not in wordList, therefore no possible transformation.

 

个人感觉这道题是相当有难度的一道题,它比之前那道 Word Ladder 要复杂很多,全场第四低的通过率 12.9% 正说明了这道题的难度,博主也是研究了网上别人的解法很久才看懂,然后照葫芦画瓢的写了出来,下面这种解法的核心思想是 BFS,大概思路如下:目的是找出所有的路径,这里建立一个路径集 paths,用以保存所有路径,然后是起始路径p,在p中先把起始单词放进去。然后定义两个整型变量 level,和 minLevel,其中 level 是记录循环中当前路径的长度,minLevel 是记录最短路径的长度,这样的好处是,如果某条路径的长度超过了已有的最短路径的长度,那么舍弃,这样会提高运行速度,相当于一种剪枝。还要定义一个 HashSet 变量 words,用来记录已经循环过的路径中的词,然后就是 BFS 的核心了,循环路径集 paths 里的内容,取出队首路径,如果该路径长度大于 level,说明字典中的有些词已经存入路径了,如果在路径中重复出现,则肯定不是最短路径,所以需要在字典中将这些词删去,然后将 words 清空,对循环对剪枝处理。然后取出当前路径的最后一个词,对每个字母进行替换并在字典中查找是否存在替换后的新词,这个过程在之前那道 Word Ladder 里面也有。如果替换后的新词在字典中存在,将其加入 words 中,并在原有路径的基础上加上这个新词生成一条新路径,如果这个新词就是结束词,则此新路径为一条完整的路径,加入结果中,并更新 minLevel,若不是结束词,则将新路径加入路径集中继续循环。写了这么多,不知道你看晕了没有,还是看代码吧,这个最有效:

 

class Solution {
public:
    vector<vector<string>> findLadders(string beginWord, string endWord, vector<string>& wordList) {
        vector<vector<string>> res;
        unordered_set<string> dict(wordList.begin(), wordList.end());
        vector<string> p{beginWord};
        queue<vector<string>> paths;
        paths.push(p);
        int level = 1, minLevel = INT_MAX;
        unordered_set<string> words;
        while (!paths.empty()) {
            auto t = paths.front(); paths.pop();
            if (t.size() > level) {
                for (string w : words) dict.erase(w);
                words.clear();
                level = t.size();
                if (level > minLevel) break;
            }
            string last = t.back();
            for (int i = 0; i < last.size(); ++i) {
                string newLast = last;
                for (char ch = 'a'; ch <= 'z'; ++ch) {
                    newLast[i] = ch;
                    if (!dict.count(newLast)) continue;
                    words.insert(newLast);
                    vector<string> nextPath = t;
                    nextPath.push_back(newLast);
                    if (newLast == endWord) {
                        res.push_back(nextPath);
                        minLevel = level;
                    } else paths.push(nextPath);
                }
            }
        }
        return res;
    }
};

 

Github 同步地址:

https://github.com/grandyang/leetcode/issues/126

 

类似题目:

Word Ladder

 

参考资料:

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

http://yucoding.blogspot.com/2014/01/leetcode-question-word-ladder-ii.html

https://leetcode.com/problems/word-ladder-ii/discuss/40487/Java-Solution-with-Iteration

 

LeetCode All in One 题目讲解汇总(持续更新中…)


转载请注明来源于 Grandyang 的博客 (grandyang.com),欢迎对文章中的引用来源进行考证,欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论,也可以邮件至 grandyang@qq.com

💰


微信打赏


Venmo 打赏

(欢迎加入博主的知识星球,博主将及时答疑解惑,并分享刷题经验与总结,试运营期间前五十位可享受半价优惠~)

×

Help us with donation