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=len1;i>=0;i){
for(int j=i+1;j<=len;j++){
if(res[j]){
if(dict.find(s.substr(i,ji))!=dict.end()){
res[i]=true;
break;
}
}
}
}
return res[0];
}
};
Share my c++ solution with only 5ms and easy to understand


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; } };