LeetCode 140 Word Break II
概述
https://leetcode.com/problems/word-break-ii/
这是一道 Hard 题。
回溯法
其实是有重复的子问题的,懒得加 cache 了。
class Solution {
public:
set<string> c;
vector<string> ans;
vector<string> wordBreak(string s, vector<string>& wordDict) {
for (auto& w : wordDict) c.insert(w);
vector<string> path = {};
helper(s, 0, path);
return ans;
}
void helper(string& s, int k, vector<string>& path) {
if (k == s.size()) {
string res;
for (int i = 0; i < path.size(); i ++) {
res += path[i];
if (i != path.size() - 1) res += " ";
}
ans.push_back(res);
return;
}
string t;
for (int i = k; i < s.size(); i ++) {
t += s[i];
if (c.count(t) != 0) {
path.push_back(t);
helper(s, i + 1, path);
path.pop_back();
}
}
}
};
Links: leetcode-140-word-break-ii