126. Word Ladder II
word II 126
2023-09-11 14:22:45 时间
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.
Approach #1: DFS. [C++]
class Solution { public: vector<vector<string>> findLadders(string beginWord, string endWord, vector<string>& wordList) { unordered_set<string> visited; unordered_set<string> wordList_(wordList.begin(), wordList.end()); vector<vector<string>> ans; queue<vector<string>> paths; paths.push({beginWord}); // record length of current shortest transformation sequence int level = 1; // record lenght of last conditional shortest transformation sequence // if the target sequence's length shorter than minLevel we break the loop. // int minLevel = INT_MAX; while (!paths.empty()) { vector<string> path = paths.front(); paths.pop(); if (path.size() > level) { for (string s : visited) wordList_.erase(s); visited.clear(); // if (path.size() > minLevel) { // break; // } level = path.size(); } string last = path.back(); for (int i = 0; i < last.length(); ++i) { string last_ = last; for (char c = 'a'; c <= 'z'; ++c) { last_[i] = c; if (wordList_.count(last_)) { vector<string> newpath = path; newpath.push_back(last_); visited.insert(last_); if (last_ == endWord) { minLevel = level; ans.push_back(newpath); } else { paths.push(newpath); } } } } } return ans; } };
Analysis:
https://leetcode.com/problems/word-ladder-ii/discuss/40434/C%2B%2B-solution-using-standard-BFS-method-no-DFS-or-backtracking
相关文章
- Word 通过添加Package 实现word藏毒
- Leetcode: Word Pattern II
- OpenXml读取word内容注意事项
- Word控件Spire.Doc 【文本】教程(10) ;在 word 文档中的字符或句子周围应用边框
- Word控件Spire.Doc 【页面背景】教程(3) ;如何在 C# 中设置单词段落底纹
- Word控件Spire.Doc 【Table】教程(4):如何在C#、VB.NET中设置Word表格样式
- Word控件Spire.Doc 【超链接】教程(3):在C#中查找word文档中的超链接
- Word控件Spire.Doc 【图像形状】教程(13): 如何在C#中对齐word文档上的形状
- Word控件Spire.Doc 【段落处理】教程(七):如如何通过在 C# 中附加 HTML 代码来设置 word 项目符号样式
- Word控件Spire.Doc 【文档操作】教程(十三):启用word文档跟踪更改
- Word控件Spire.Doc 【文档操作】教程(十二):在 C# 中接受/拒绝 word 文档的跟踪更改
- Word控件Spire.Doc 转换教程(二十):在 C#、VB.NET 中将 Word 转换为 Word XML
- Word处理控件Aspose.Words功能演示:在 Python 中将 Word 文档转换为 EPUB
- Word Art In Bash
- Excel自动化教程之通过python将Excel与Word集成无缝生成自动报告
- SpringBoot导出Word方式二:根据Word模板动态生成word(easypoi)
- SpringBoot导出Word方式一:根据Word模板动态生成word(Poi-tl)
- python word 插入转下页及接上页(win32com)
- Unity 之 实现读取代码写进Word文档功能实现 -- 软著脚本生成工具
- Vue脚手架报错: Component name “xxx“ should always be multi-word(vue/multi-word-component-names)的解决办法
- word 取消重新开始页码如何设置、标题另起一页问题
- [LintCode] Length of Last Word 求末尾单词的长度
- ABP word下载 模板替换 文件下载
- 140. Word Break II
- 212. Word Search II