单词拆分2，递归+dp,

需要使用递归，同时使用记忆化搜索保存下来结果，c++代码如下

 

1 class Solution { 2 public: 3     //定义一个子串和子串拆分（如果有的话）的映射 4     unordered_map
     
      
       >m; 5     vector
       
         wordBreak(string s, vector
        
         & wordDict) { 6         if(m.count(s)) return m[s];//当映射的子串有s说明已经判断完了返回拆分m[s] 7         if(s.empty()) return {
   ""};//假如s是空的返回空串 8         vector
         
           res; 9         for(string word: wordDict){10             if(s.substr(0,word.size())!=word) continue;//在s开头找到字典中的词；11             vector
          
            rem=wordBreak(s.substr(word.size()),wordDict);//rem是剩下的子串拆分，递归调用wordBreak12 for(string str:rem){13 res.push_back(word+(str.empty() ? "" : " ")+str);//str非空时，前面加个空格后面再加单词；14 }15 }16 return m[s]=res;17 }18 };
          
         
        
       
      
     

参考：