# C++ solution using dfs + dp + and graph

• `dp[i]` is using the same approach from word break to determine if `[0, i - 1]` can be built using dictionary. Then for each `i`, build adjacency lists `adj` for all the possible `j` that `[i, j]` is a word in dictionary, so now it's like to solve a graph problem. This may not be the most optimal compared to other 4 ms solutions, just to share. For improvement, as suggested by other posts, find the `minlen`, `maxlen` of word length in dictionary can definitely cut down the run time in loop when building adj lists.

8 ms (with improvement)

``````class Solution {
public:
vector<string> wordBreak(string s, unordered_set<string>& wordDict) {
vector<string> all;
int n = s.size(), i, minLen = INT_MAX, maxLen = INT_MIN;
vector<bool> dp(n + 1, false);

for(auto word: wordDict){
minLen = min(minLen, (int)word.size());
maxLen = max(maxLen, (int)word.size());
}
// build dp and adj at the same time
for(i = 0, dp[0] = true; i < n; i++){
for(int len = minLen; len <= min(maxLen, n - i); len++){
if(dp[i] && wordDict.find(s.substr(i, len)) != wordDict.end()){
dp[i + len] = true;
}
}
}

if(dp[n]) dfs(s, 0, "", all, dp, adj);
return all;
}

void dfs(string s, int start, string oneSol, vector<string>& all, vector<bool>& dp, vector<vector<int>> &adj)
{
if(!dp[start]) return;
string word = s.substr(start, i - start + 1);
if(i == s.size() - 1) {
all.push_back(oneSol + word);
return;
}
dfs(s, i + 1, oneSol + word + " ", all, dp, adj);
}
}
};
``````

24 ms

``````class Solution {
public:
vector<string> wordBreak(string s, unordered_set<string>& wordDict) {
vector<string> all;
int n = s.size();

vector<bool> dp(n + 1, false);
dp[0] = true;

for(int i = 0; i < s.size(); i++){
for(int j = i; j < s.size(); j++){
if(dp[i] && wordDict.find(s.substr(i, j - i + 1)) != wordDict.end()){
dp[j + 1] = true;
}
}
}

if(dp[n]) dfs(s, 0, "", all, dp, adj);
return all;
}

void dfs(string s, int start, string oneSol, vector<string>& all, vector<bool>& dp, vector<vector<int>> &adj)
{
if(!dp[start]) return;
string word = s.substr(start, i - start + 1);
if(i == s.size() - 1) {
all.push_back(oneSol + word);
return;
}
dfs(s, i + 1, oneSol + word + " ", all, dp, adj);
}
}
};``````

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