8 ms C++ solution with explanation -- dp; no recursion

• This solution is a two-stage dynamic program. First: we use the solution from the Word Break problem to find all the break points -- the positions where we might possibly insert a space. The second dynamic program then builds up the actual solution by skipping through the break-points.

Note: comments use python-like notation to indicate substrings. That is: s[:i] is the substring of s from position 0 up to, but not including, position j.

``````vector<string> wordBreak(string s, unordered_set<string>& wordDict) {
int n = s.size();
if (n == 0)
return {};

// First: identify the break points (and that there exists at least one way to break it).
// D[i] = True if it is possible to break up s[:i] in at least one way.
vector<bool> D(n+1, false);
D[0] = true;
for (int i=1; i <= n; i++) {
for (int j=i-1; j >= 0 && D[i] == false; j--) {
D[i] = D[j] && wordDict.find(s.substr(j, i-j)) != wordDict.end();
}
}

if (!D[n])  // There is no solution.
return {};

// Find the i such that D[i] is true.
// In given example: break_points = [0,3,4,7,10].
vector<int> break_points;
for (int i=0; i < D.size(); i++) {
if (D[i]) {
break_points.push_back(i);
}
}

int m = break_points.size();

// Now find the solution based on the breakpoints.
// E[i]: Set of all strings we can create using s[:break_points[i]].
// In the example: E[0] = [""], E[1] = ["cat"], E[2] = ["cats"], E[3] = ["cats and", cat sand"]
vector<vector<string>> E(m);
E[0] = {""};
for (int i = 0; i < m; i++) {
for (int j=i-1; j >=0; j--) {  // Will now compute E
// t is the string defined from breakpoints i to j
string t = s.substr(break_points[j], break_points[i] - break_points[j]);
if (wordDict.find(t) != wordDict.end()) {
for (auto& u : E[j])
E[i].push_back(u + " " + t);
}
}
}

// Need to chop off the extra " " at the start of each string in E[m-1]
vector<string> R;
transform(E[m-1].begin(), E[m-1].end(), back_inserter(R), [](string& s) {return s.substr(1,s.size()-1);});
return R;
}``````

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