# My double DP solution: C++ with solving TLE and MLE

• ``````class Solution {
public:
vector<string> wordBreak(string s, unordered_set<string> &dict);
};

vector<string> Solution::wordBreak(string s, unordered_set<string> &dict) {
int n = s.size();
vector<bool> f; // 0 --> n - 1
f.resize(n + 1);
f[n] = true;
for (int i = n - 1; i >= 0; -- i) {
string p = s.substr(i, 1);
f[i] = false;
for (int j = i + 1; j < n; ++ j) {
if (f[j] && dict.find(p) != dict.end()) {
f[i] = true;
break;
}
p = p + s[j];
}
if (!f[i])
f[i] = dict.find(p) != dict.end();
}

// 1 --> n
vector<string> ret[n + 1];
ret[0].clear();
if (!f[0]) return ret[0];
ret[0].push_back("");
for (int i = 1; i <= n; ++ i) {
ret[i].clear();
if (!f[i]) continue;
string p = s.substr(i - 1, 1);
for (int j = i - 1; j > 0; -- j) {
if (!ret[j].empty() && dict.find(p) != dict.end()) {
for (int k = 0; k < ret[j].size(); ++ k)
ret[i].push_back(ret[j][k] + " " + p);
}
p = s[j - 1] + p;
}
if (dict.find(p) != dict.end())
ret[i].push_back(p);
}
return ret[n];
}``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.