[LeetCode] Word Break II 拆分词句之二
Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, add spaces in s to construct a sentence where each word is a valid dictionary word. Return all such possible sentences.
Note:
- The same word in the dictionary may be reused multiple times in the segmentation.
- You may assume the dictionary does not contain duplicate words.
Example 1:
Input: s = "catsanddog
" wordDict =["cat", "cats", "and", "sand", "dog"]
Output:[ "cats and dog", "cat sand dog" ]
Example 2:
Input: s = "pineapplepenapple" wordDict = ["apple", "pen", "applepen", "pine", "pineapple"] Output: [ "pine apple pen apple", "pineapple pen apple", "pine applepen apple" ] Explanation: Note that you are allowed to reuse a dictionary word.
Example 3:
Input: s = "catsandog" wordDict = ["cats", "dog", "sand", "and", "cat"] Output: []
这道题是之前那道Word Break 拆分词句的拓展,那道题只让我们判断给定的字符串能否被拆分成字典中的词,而这道题加大了难度,让我们求出所有可以拆分成的情况,就像题目中给的例子所示。之前的版本中字典wordDict的数据类型是HashSet,现在的不知为何改成了数组vector,而且博主看到第二个例子就笑了,PPAP么,哈哈~
根据老夫行走江湖多年的经验,像这种返回结果要列举所有情况的题,十有八九都是要用递归来做的。当我们一时半会没有啥思路的时候,先不要考虑代码如何实现,如果就给你一个s和wordDict,不看Output的内容,你会怎么找出结果。比如对于例子1,博主可能会先扫一遍wordDict数组,看有没有单词可以当s的开头,那么我们可以发现cat和cats都可以,比如我们先选了cat,那么此时s就变成了 "sanddog",我们再在数组里找单词,发现了sand可以,最后剩一个dog,也在数组中,于是一个结果就出来了。然后回到开头选cats的话,那么此时s就变成了 "anddog",我们再在数组里找单词,发现了and可以,最后剩一个dog,也在数组中,于是另一个结果也就出来了。那么这个查询的方法很适合用递归来实现,因为s改变后,查询的机制并不变,很适合调用递归函数。再者,我们要明确的是,如果不用记忆数组做减少重复计算的优化,那么递归方法跟brute force没什么区别,大概率无法通过OJ。所以我们要避免重复计算,如何避免呢,还是看上面的分析,如果当s变成 "sanddog"的时候,那么此时我们知道其可以拆分成sand和dog,当某个时候如果我们又遇到了这个 "sanddog"的时候,我们难道还需要再调用递归算一遍吗,当然不希望啦,所以我们要将这个中间结果保存起来,由于我们必须要同时保存s和其所有的拆分的字符串,那么可以使用一个HashMap,来建立二者之间的映射,那么在递归函数中,我们首先检测当前s是否已经有映射,有的话直接返回即可,如果s为空了,我们如何处理呢,题目中说了给定的s不会为空,但是我们递归函数处理时s是会变空的,这时候我们是直接返回空集吗,这里有个小trick,我们其实放一个空字符串返回,为啥要这么做呢?我们观察题目中的Output,发现单词之间是有空格,而最后一个单词后面没有空格,所以这个空字符串就起到了标记当前单词是最后一个,那么我们就不要再加空格了。接着往下看,我们遍历wordDict数组,如果某个单词是s字符串中的开头单词的话,我们对后面部分调用递归函数,将结果保存到rem中,然后遍历里面的所有字符串,和当前的单词拼接起来,这里就用到了我们前面说的trick。for循环结束后,记得返回结果res之前建立其和s之间的映射,方便下次使用,参见代码如下:
解法一:
class Solution { public: vector<string> wordBreak(string s, vector<string>& wordDict) { unordered_map<string, vector<string>> m; return helper(s, wordDict, m); } vector<string> helper(string s, vector<string>& wordDict, unordered_map<string, vector<string>>& m) { if (m.count(s)) return m[s]; if (s.empty()) return {""}; vector<string> res; for (string word : wordDict) { if (s.substr(0, word.size()) != word) continue; vector<string> rem = helper(s.substr(word.size()), wordDict, m); for (string str : rem) { res.push_back(word + (str.empty() ? "" : " ") + str); } } return m[s] = res; } };
我们也可以将将主函数本身当作递归函数,这样就不用单独的使用一个递归函数了,不过我们的HashMap必须是全局了,写在外部就好了,参见代码如下:
解法二:
class Solution { public: unordered_map<string, vector<string>> m; vector<string> wordBreak(string s, vector<string>& wordDict) { if (m.count(s)) return m[s]; if (s.empty()) return {""}; vector<string> res; for (string word : wordDict) { if (s.substr(0, word.size()) != word) continue; vector<string> rem = wordBreak(s.substr(word.size()), wordDict); for (string str : rem) { res.push_back(word + (str.empty() ? "" : " ") + str); } } return m[s] = res; } };
类似题目:
参考资料:
https://leetcode.com/problems/word-break-ii/description/
https://leetcode.com/problems/word-break-ii/solution/
相关文章
- Leetcode: Minimum Unique Word Abbreviation
- Leetcode: Valid Word Abbreviation
- Leetcode: Kth Smallest Element in a Sorted Matrix
- Leetcode: Word Pattern II
- Leetcode: Word Pattern
- Leetcode: Graph Valid Tree && Summary: Detect cycle in undirected graph
- Leetcode: Word Ladder II
- Word控件Spire.Doc 【页眉页脚】教程(10): 锁定标题以防止在 C# 中编辑 word 文档
- Word控件Spire.Doc 【页面背景】教程(4) ;如何在word文档的一侧创建垂直表格
- Word控件Spire.Doc 【图像形状】教程(12) 如何在C#中旋转word文档上的形状
- Word控件Spire.Doc 【段落处理】教程(十二):如何在 C# 中管理 word 文档的分页
- Word控件Spire.Doc 【表单域】教程(六):C#在word文档中插入和删除TOC
- JS Leetcode 530. 二叉搜索树的最小绝对差 题解分析,再次了解中序遍历
- [LeetCode]460.LFU缓存机制
- [LeetCode] Word Break II
- [LeetCode] Distinct Subsequences
- [LeetCode] Word Break
- [LeetCode] Word Ladder
- 135、【贪心算法】leetcode ——135. 分发糖果(多维度贪心)(C++版本)
- 【LeetCode】Largest Number
- 【LeetCode】140. Word Break II
- [LeetCode] 872. Leaf-Similar Trees 叶结点相似的树
- [LeetCode] Stickers to Spell Word 贴片拼单词
- [LeetCode] 362. Design Hit Counter 设计点击计数器
- [LeetCode] 291. Word Pattern II 词语模式之二
- [LeetCode] 212. Word Search II 词语搜索之二
- leetcode 206. Reverse Linked List 反转链表(简单)
- leetcode 79. Word Search 单词搜索
- leetcode 524. Longest Word in Dictionary through Deleting 通过删除字母匹配到字典里最长单词