# Evolve from brute force

1. O(2^n)
``````    vector<string> wordBreak(string s, unordered_set<string>& wordDict) {
vector<string> res;
string one;
wordBreak(0,one,s,wordDict,res);
return res;
}
void wordBreak(int p, string &pre, string& s, unordered_set<string>& wordDict,vector<string>& res) {
int n = s.size();
if(p==n) {
pre.pop_back();
res.push_back(pre);
}
string cur;
int sz = pre.size();
for(int i=p;i<n;i++)
if(wordDict.count(cur+=s[i])) {
pre+=cur;
pre+=' ';
wordBreak(i+1, pre,s,wordDict,res);
pre.resize(sz);
}
}
``````
1. Memorization. Break each substr only once and cache the results.
``````    vector<string> wordBreak(string s, unordered_set<string>& wordDict) {
unordered_map<int,vector<string>> mem({{s.size(),vector<string>()}});
wordBreak(0,s,wordDict,mem);
return mem[0];
}
void wordBreak(int p, string& s, unordered_set<string>& wordDict, unordered_map<int,vector<string>>& mem) {
if(mem.count(p)) return;
string cur;
mem[p];
int n = s.size();
for(int i=p;i<n;i++) {
if(!wordDict.count(cur+=s[i])) continue;
wordBreak(i+1, s,wordDict,mem);
if(i==n-1) {
mem[p].push_back(cur);
continue;
}
vector<string> &v = mem[i+1];
for(string s:v) mem[p].push_back(cur+' '+s);
}
}
``````
1. Another way to improve #1 is pre-computing the break points and then search from the break points only.
``````    vector<string> wordBreak(string s, unordered_set<string>& wordDict) {
int n=s.size();
vector<bool> canBrk(n+1,false);
canBrk[n]=true;
for(int i=n-1;i>=0;i--) {
string ss;
for(int j=i;j<n;j++) {
ss+=s[j];
if(!wordDict.count(ss)||!canBrk[j+1]) continue;
canBrk[i]=true;
break;
}
}
vector<string> res;
string one;
recur(0,one,s,canBrk,wordDict, res);
return res;
}
void recur(int id,string &cur,string &s,vector<bool>& canBrk, unordered_set<string>& wordDict,vector<string> &res) {
if(!canBrk[id]) return;
int n=s.size();
if(id==n) {
cur.pop_back();
res.push_back(cur);
return;
}
int cs=cur.size();
string ss;
for(int i=id;i<n;i++) {
ss+=s[i];
cur+=s[i];
if(!wordDict.count(ss)) continue;
cur+=' ';
recur(i+1,cur,s,canBrk,wordDict,res);
cur.pop_back();
}
cur.erase(cs);
}
``````

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