Open GH1995 opened 5 years ago
让我们求出所有可以拆分成的情况
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;
}
};
140. Word Break II
Difficulty: Hard
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:
Example 1:
Example 2:
Example 3: