# Share my c++ solution with only 5ms and easy to understand

• ``````class Solution {
public:
bool wordBreak(string s, unordered_set<string> &dict) {
int len=s.size();
vector<bool >res(len,false);
res.push_back(true);
for(int i=len-1;i>=0;i--){
for(int j=i+1;j<=len;j++){
if(res[j]){
if(dict.find(s.substr(i,j-i))!=dict.end()){
res[i]=true;
break;
}
}
}
}
return res[0];
}
};``````

• Your solution is much more compact than one I read before. Compared with that one, yours takes less space. Moreover, I guess this one also needs less time. Thank you for your sharing.

• In addition, we should calculate the effective length of the substring, here is my 0ms DP solution:

``````class Solution {
public:
bool wordBreak(std::string s, std::unordered_set<std::string> &dict) {
if (dict.empty())
return false;
int len = s.size(), max_len = dict.begin()->size(), min_len = max_len;
for (auto it = dict.begin(); it != dict.end(); ++it)
if (it->size() > max_len)
max_len = it->size();
else if (it->size() < min_len)
min_len = it->size();
std::vector<int> flag(len + 1);
flag[len] = 1;
for (int i = len - 1; i >= 0; --i)
for (int j = min_len; j <= std::min(max_len, len - i); ++j)
if (flag[i + j] && dict.find(s.substr(i, j)) != dict.end()) {
flag[i] = 1;
break;
}
return flag[0] == 1;
}
};``````

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