# [23ms] C++ sln, dp + DFS

• ``````class Solution {
public:
vector<string> wordBreak(string s, vector<string>& wordDict)
{

for(auto s:wordDict)
{
dict.insert(s);
}
int len = s.size();

vector<vector<bool>> T(len,vector<bool>(len,false));
// scan different length of substring, start from 1 (bottom) to len(top), bottom-up dp sln
for(int l = 1; l<=len; l++)
{
for(int i = 0; i<=len-l; i++)
{
// i is the row index and j is the column index of the table T
// meaning currently we are solve subproblem of substring s[i:j]
int j = i+l-1;
// get the substring with lenght l: s[i:j]
string tps = s.substr(i,l);
if(dict.find(tps)!=dict.end())
T[i][j] = true;
else
for(int k = i;k<j;k++)
if(T[i][k]==true && T[k+1][j]==true)
{
T[i][j] = true;
break;
}
}
}
string temp = "";
reconSln(s,temp,T,0);
return memory;
}
private:
vector<string> memory;
unordered_set<string> dict;

// reconstruct the solution of the dp, with DFS
// string s is the original string, temp is a helper variable for recursive method
void reconSln(string s, string temp,vector<vector<bool>> T, int depth)
{
int col = T[0].size();
for(int i = depth; i<col; i++)
if (T[depth][i] == true && dict.count(s.substr(depth,i-depth+1)))
{
// DFS
if(i!=col-1)
{
string p = temp + s.substr(depth,i-depth+1) + " ";
// iff T[i+1][col-1]==true, that branch may have a solution
if(T[i+1][col-1]==true)
reconSln(s,p,T,i+1);
}
else // bottom of DFS
{

string rs = temp + s.substr(depth); // the last word of the string
memory.push_back(rs);
}
}
}
};``````

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