[LeetCode] 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:
- Only one letter can be changed at a time
- 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
类似题目:
参考资料:
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: Shortest Word Distance
- Word控件Spire.Doc 【书签】教程(6): 设置word文档中不同级别书签的颜色
- Word控件Spire.Doc 【Table】教程(7): 如何在C#中用表格替换word文档中的文本
- Word控件Spire.Doc 转换教程(二十一):将非标准字体的word文档转换为PDF
- Word控件Spire.Doc 【Table】教程(13): 如何在 C# 中向现有的 word 表添加一行
- LeetCode高频题互联网大厂笔试题:手撕k-means聚类算法:python代码实现
- [LeetCode] Word Ladder II
- 【LeetCode】140. Word Break II
- [LeetCode] 1192. Critical Connections in a Network 查找集群内的关键连接
- [LeetCode] 1154. Day of the Year 一年中的第几天
- [LeetCode] Contain Virus 包含病毒
- [LeetCode] Maximum Average Subarray I 子数组的最大平均值
- [LeetCode] 379. Design Phone Directory 设计电话目录
- [LeetCode] Word Frequency 单词频率
- [LeetCode] Add and Search Word - Data structure design 添加和查找单词-数据结构设计
- [LeetCode] 10. Regular Expression Matching 正则表达式匹配
- [LeetCode] Bitwise AND of Numbers Range 数字范围位相与
- leetcode 696. Count Binary Substrings 计数二进制子串(简单)
- leetcode 79. Word Search 单词搜索