C++ | Leetcode C++题解之第140题单词拆分II
题目:
题解:
class Solution {
private:
unordered_map<int, vector> ans;
unordered_set wordSet;
public:
vector wordBreak(string s, vector& wordDict) {
wordSet = unordered_set(wordDict.begin(), wordDict.end());
backtrack(s, 0);
return ans[0];
}
void backtrack(const string& s, int index) {
if (!ans.count(index)) {
if (index == s.size()) {
ans[index] = {""};
return;
}
ans[index] = {};
for (int i = index + 1; i <= s.size(); ++i) {
string word = s.substr(index, i - index);
if (wordSet.count(word)) {
backtrack(s, i);
for (const string& succ: ans[i]) {
ans[index].push_back(succ.empty() ? word : word + " " + succ);
}
}
}
}
}
};