- 单词拆分 II
给定一个非空字符串 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”]
输出: []
简单递归写法
会超时：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| class Solution {
public:
vector<string> wordBreak(string s, vector<string>& wordDict) {
vector<string> ans;
for (auto i = wordDict.begin(); i != wordDict.end(); i++) {
if (s.rfind(*i, 0) == 0) {
if (s.size() == (*i).size()) {
ans.push_back(*i);
}
else {
auto m = wordBreak(s.substr((*i).size()), wordDict);
for (auto t = m.begin(); t != m.end(); t++) {
ans.push_back(*i + " " + *t);
}
}
}
}
return ans;
}
};
|
加上记录，不多算
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
| class Solution {
public:
map<int, vector<string>> memo;
vector<string> wordBreakIndex(string& s, vector<string>& wordDict, int index) {
if (memo.find(index) != memo.end()) {
return memo[index];
}
vector<string> ans;
for (auto i = wordDict.begin(); i != wordDict.end(); i++) {
if (s.rfind(*i, index) == index) {
if (s.size() == index + (*i).size()) {
ans.push_back(*i);
}
else {
auto m = wordBreakIndex(s, wordDict, index + (*i).size());
for (auto t = m.begin(); t != m.end(); t++) {
ans.push_back(*i + " " + *t);
}
}
}
}
memo[index] = ans;
return ans;
}
vector<string> wordBreak(string s, vector<string>& wordDict) {
memo.clear();
return wordBreakIndex(s, wordDict, 0);
}
};
|
结果是：
1
2
| 执行用时 : 112 ms, 在所有 C++ 提交中击败了5.27%的用户
内存消耗 : 11.2 MB, 在所有 C++ 提交中击败了77.66%的用户
|