# CPP DP solution, 3ms beats 81%

• DP solution, clear comment

``````class Solution {
public:
//helper function to sort
bool static comp(string &a,string &b){
return a.length()<b.length();
}
bool wordBreak(string s, vector<string>& wordDict) {
//description said nonempty,it's a lie
if(s.length()==0||wordDict.size()==0)
return false;

int slen = s.length();
vector<string> tv;
//if found any wordDict item in string,save it
for(auto i:wordDict){
if(s.find(i)!=string::npos){
tv.push_back(i);
}
}
//be sure this vector is nonempty
if(tv.size()==0)
return false;

//sort by length of item
sort(tv.begin(),tv.end(),comp);
//dp[i] means can items in wordDict make up s.substr(0,i)
vector<bool> dp(slen+1,false);
dp[0] = true;
//the sorted vector tv,tv[0] is the least length
for(int i = tv[0].length();i<=slen;i++){
for(auto str:tv){
int l = str.length();
//length of str may be larger than i,skip it
if(i>=l){
//s.substr(0,i) = s.substr(0,i-l)+s.substr(i-1,l)
//so we just need to know whether these two parts are both true
dp[i]=dp[i-l]&&(s.substr(i-l,l)==str);
//once true,save it and break
if(dp[i])
break;
}
}
}
return dp[slen];
}
};
``````

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