阅读量:0
力扣139.单词拆分
记忆化搜索
从后往前枚举拆分点，如果拆完剩下的在字典中有，就继续dfs前面剩余字符串
-
class Solution { public: bool wordBreak(string s, vector<string>& wordDict) { int n = s.size(); unordered_set<string> cnt = {wordDict.begin(),wordDict.end()}; vector<int> memo(n,-1); //dfs的内联函数写法 && auto dfs = [&](auto &&dfs,int i)->bool{ if(i<0) return true; //初始化为-1 if(memo[i] != -1) return memo[i]; bool ok = false; //枚举拆分点 for(int k=i;k>=0;k--) { string sub = s.substr(k,i-k+1); ok = ok || (cnt.contains(sub) && dfs(dfs,k-1)); if(ok) return memo[i] = true; } return memo[i] = false; }; return dfs(dfs,n-1); } };
1:1递推
-
class Solution { public: bool wordBreak(string s, vector<string>& wordDict) { int n = s.size(); unordered_set<string> cnt = {wordDict.begin(),wordDict.end()}; vector<bool> f(n+1,false); f[0] = true; for(int i=0;i<n;i++) { bool ok = false; for(int k=i;k>=0;k--) { string sub = s.substr(k,i-k+1); ok = ok || (cnt.contains(sub) && f[k]); if(ok) { f[i+1] = true; break; } } } return f[n]; } };
