# 8ms C++ Solution, dp and recursion

• I use quite a few vectors and sets, trying to speed up the calculation.

``````class Solution {
private:
void split( vector<bool>& dp, unordered_set<string>& wordDict, unordered_set<int>& lenset,
int index, string& s, vector<string>& ans, vector<string>& buf ) {
for( int len : lenset ) {
if( len > s.length() - index ) continue;
if( !dp[index + len] ) continue;
string sub = s.substr( index, len );
if( wordDict.find(sub) == wordDict.end() ) continue;
buf.push_back(sub);
if( len == s.length() - index ) {
string tmp = buf[0];
for( int i=1; i<buf.size(); i++ ) {
tmp.append(" ");
tmp.append(buf[i]);
}
ans.push_back(tmp);
} else split( dp, wordDict, lenset, index + len, s, ans, buf );
buf.pop_back();
}
}
public:
vector<string> wordBreak(string s, unordered_set<string>& wordDict) {
vector<string> ans, buf;
vector<bool> dp(s.length()+1);
dp[0] = true;
for( int i=1; i<s.length()+1; i++ ) {
for( int j=i-1; j>=0; j-- ) {
if( dp[j] && wordDict.find(s.substr(j,i-j)) != wordDict.end() ) {
dp[i] = true;
break;
}
}
}
if( !dp[s.length()] ) return ans;
unordered_set<int> lenset;
for( string str : wordDict ) lenset.insert(str.length());
split(dp, wordDict, lenset, 0, s, ans, buf);
return ans;
}
};``````

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