难度 hard
给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict,在字符串中增加空格来构建一个句子,使得句子中所有的单词都在词典中。返回所有这些可能的句子。
说明:
分隔时可以重复使用字典中的单词。
你可以假设字典中没有重复的单词。
示例 1:
输入:
s = "catsanddog"
wordDict = ["cat", "cats", "and", "sand", "dog"]
输出:
[
"cats and dog",
"cat sand dog"
]
示例 2:
输入:
s = "pineapplepenapple"
wordDict = ["apple", "pen", "applepen", "pine", "pineapple"]
输出:
[
"pine apple pen apple",
"pineapple pen apple",
"pine applepen apple"
]
解释: 注意你可以重复使用字典中的单词。
示例 3:
输入:
s = "catsandog"
wordDict = ["cats", "dog", "sand", "and", "cat"]
输出:
[]
解题思路:这道题目和139. Word Break 拆分词句这道题目是非常接近的,可以参考那边的解法二,使用递归的方法,用一个List保存满足条件的单词,当遍历到最后一个字符的时候,就把所有单词组合成句子,然后添加到res中。需要注意的一点就是,保存单词的数组List,在每轮递归的时候都要给它new一个新的List出来,并用out初始化,因为java中List传递的是地址,如果已经遍历完了字符串,然后将out组成句子添加到res中,out此时是满足条件的一些单词的集合,不能直接clear,也不能简单地去除最后一个单词,以s = "pineapplepenapple",
wordDict = ["apple", "pen", "applepen", "pine", "pineapple"],这个例子为例,完整答案应该是[
"pine apple pen apple",
"pineapple pen apple",
"pine applepen apple"
],如果简单地clear,把out清空,就会出现"pine applepen apple"这个答案变成了"applepen apple",因为前面的"pine"部分已经遍历过了,在组成第一个句子的时候又被清走了,最后答案中也漏掉了这个单词。所以应该新建一个List对象,用out初始化,保证每个递归函数传进来的out都有唯一地址,这样就不会相互干扰了。
代码t99 s81 java
class Solution {
public List<String> wordBreak(String s, List<String> wordDict) {
int len = s.length();
HashSet<String> set = new HashSet<>();
set.addAll(wordDict);
List<String> res = new ArrayList<>();
List<String> out = new ArrayList<>();
helper(s, 0, set, res, out);
return res;
}
public void helper(String s, int st, HashSet<String> set, List<String> res, List<String> out){
int len = s.length();
if(st>=len){
String sentence = buildSentence(out);
res.add(sentence);
return;
}
for(int i=st+1; i<=len; i++){
if(set.contains(s.substring(st, i))){
// System.out.println("st: "+st+" i: "+i);
List<String> t = new ArrayList<>(out);
t.add(s.substring(st, i));
helper(s, i, set, res, t);
}
}
}
public String buildSentence(List<String> out){
StringBuffer sb = new StringBuffer();
for(int i=0; i<out.size(); i++){
sb.append(out.get(i));
if(i<out.size()-1) sb.append(" ");
}
return sb.toString();
}
}
下面这个是4个月前提交的cpp版本的,简洁很多。
代码
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;
}
};
参考资料: