# If feel this problem Complex, this piece of Readable Codes with Explanatory Notes May Help

• class Solution {
public:
void wordBreak_add(string &origin, vector<vector<int> > &Edges, int L,
string current, int curPos, vector<string> &ans )
{
for(int i = 0; i < Edges[curPos].size(); i ++)
{
int nextPos = Edges[curPos][i];
string next = current;
/* add a word to the current piece of string,
for further comprising of some valid sentences */
if(curPos == 0)
{
next = origin.substr(curPos, nextPos - curPos);
}
else
{
next += (string(" ") + origin.substr(curPos, nextPos - curPos));
}

/* nextPos == L means you get a kind of valid sentences */
if(nextPos == L)ans.push_back(next);
else wordBreak_add(origin, Edges, L, next, nextPos, ans);
}
}
vector<string> wordBreak(string s, unordered_set<string> &dict) {
vector<string> ans;
int L=s.length();
if(L<1)return ans;

/* sig[i] == ture means:
s.substr(i, L -i) could be a string has valid wordBreak solutions */
bool *sig=new bool[L+5];
memset(sig,0,L);

/* Any element of Edges[curPos] nextPos means:
s.substr(curPos, nextPos-curPos) is a word in the dictionary,
and sig[nextPos] == true,
from these two conditions, you can derive valid sentences.
Especially, when nextPos == L, then you get a kind of whole valid sentences.*/
vector<vector<int> > Edges;
for(int i = 0; i < L; i ++)Edges.push_back(vector<int>());

/* Do dynamic programming from the back,
sig[0] == true means the original string s has valid wordBreak solutions */
for(int i = L-1; i >= 0; i --)
{
if(dict.find(s.substr(i, L-i)) != dict.end())
{
sig[i] = true;
Edges[i].push_back(L);
}
if(sig[i])
{
for(int j = i-1; j >= 0; j --)
{
if(dict.find(s.substr(j,i-j)) != dict.end()){
Edges[j].push_back(i);
sig[j] = true;
}
}
}
}

if(!sig[0])
{
delete[] sig;
return ans; //no valid solution
}

delete[] sig;
/* Use recursive function to derive all the solutions,
the complexity is unavoidable, since all the solutions must be made.*/
wordBreak_add(s, Edges, L, string(), 0, ans);
return ans;
}
};

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