**In order to avoid checks unnecessary substring, we should calculate the effective length of the substring at first.**

The follow is my accepted DP solution, and the return running time is 0ms.

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