与Word Break II(参见这篇文章)相比,只需要判断是否可行,不需要构造解,简单一些。
依然是动态规划。
代码:
bool wordBreak(string s, unordered_set<string> &dict) {
int maxLen = ;
for (auto w : dict)
maxLen = maxLen > w.length() ? maxLen : w.length(); vector<bool> res(s.length() + , false);
res[s.length()] = true; for (int i = s.length() - ; i >= ; i--) {
for (int l = ; !res[i] && l <= maxLen && i + l <= s.length(); l++)
res[i] = dict.find(s.substr(i, l)) != dict.end() && res[i + l];
} return res[];
}