题目描述
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.
Example1:
Input: s = "catsanddog" wordDict = ["cat", "cats", "and", "sand", "dog"] Output: [ "cats and dog", "cat sand dog" ]
Example2:
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.
Example3:
Input: s = "catsandog" wordDict = ["cats", "dog", "sand", "and", "cat"] Output: []
NOTE
- All inputs are consist of lowercase letters a-z.
- The values of words are distinct.
解题思路
- 参考
- 递归搜索
-
使用一个hashmap建立映射结果
- 具体过程：
- 先扫一遍wordDict数组，
- 看有没有单词可以当s的开头，那么我们可以发现cat和cats都可以，
- 比如我们先选了cat，那么此时s就变成了 “sanddog”，我们再在数组里找单词，发现了sand可以，最后剩一个dog，也在数组中，于是一个结果就出来了。
- 然后回到开头选cats的话，那么此时s就变成了 “anddog”，我们再在数组里找单词，发现了and可以，最后剩一个dog，也在数组中，于是另一个结果也就出来了。那么这个查询的方法很适合用递归来实现，因为s改变后，查询的机制并不变，很适合调用递归函数。
- 观察题目中的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.size() == 0){
return {""}; // 这里是递归结束返回的结果
}
vector<string> res;
for(auto word : wordDict){
if(s.substr(0, word.size()) != word){ // 根据wordDict里面的单词，查s，是否相等
continue;
}
vector<string> rem = helper(s.substr(word.size()), wordDict, m);
for(string str : rem){
res.push_back(word + (str == "" ? "" : " ") + str);
}
}
m[s] = res;
return m[s];
}
};
