力扣139.单词拆分

记忆化搜索

• 从后往前枚举拆分点，如果拆完剩下的在字典中有，就继续dfs前面剩余字符串

•   class Solution {   public:       bool wordBreak(string s, vector& wordDict) {           int n = s.size();           unordered_set cnt = {wordDict.begin(),wordDict.end()};           vector 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& wordDict) {               int n = s.size();               unordered_set cnt = {wordDict.begin(),wordDict.end()};               vector f(n+1,false);               f[0] = true;               for(int i=0;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];           }       };