本文共 2066 字，大约阅读时间需要 6 分钟。

思路：

首先想到的是递归的解法，但是考虑到TLE的问题，此路不通。其次是动态规划的版本，结合139 Word Break ，只需扩展那个动态数组就可以了。139中用一个bool数组表示dp[i]之前的串能否形成切分。那么在这个问题中，可以将最后一个成功切出来的单词挂在i角标的下面。

这时，最好用一个vector<string>的数组来存储最后一个切下的单词。

这样先用动态规划扫一遍之后，会得到上图的结构。

然后用dfs从后向前路径搜索，找到e下的“code”通过他的长度就能找到下一个位置t，以此类推，直到游标越出边界递归到达终点。

谈谈走的弯路：

因为引用了139中的代码，所以一开始误以为dp[i]==true且新切下来的串在字典中就可以挂在i位置，但这样的话有很多多余的路径，导致TLE。直到最后那个很长的case才发现了这一点，究其原因还是思路上模糊了。用了一个多小时才定位到这个问题。。。郁闷。

vector
   
     result;void dfsLoadResult(int i, vector
    
     * carry, vector
     
       pro){//填充结果	//i表示以i角标为结束范围,pro记录着过程中的单词	if (i<0){		return;	}	if (i == 0){//一个有效解，向result装填		int prolen = pro.size();		if (prolen == 0){			return;		}		string ts = "";		ts = ts + pro[prolen - 1];		for (int i = prolen - 2; i >= 0; i--){			ts = ts + " " + pro[i];		}		result.push_back(ts);		return;	}	int carrylen = carry[i].size();//查看i下挂了几个单词	if (carrylen == 0){		return;	}	for (int k = 0; k < carrylen; k++){		int ti = carry[i][k].size();//i下第k个单词的长度		vector
      
        tepro = vector
       
        (pro);		tepro.push_back(carry[i][k]);		dfsLoadResult(i - ti, carry, tepro);	}}//*************************辅助**************************//vector
        
          wordBreak(string s, unordered_set
         
          & wordDict) { result.clear(); int slen = s.size(); if (slen == 0){ return result; } else if (wordDict.size() == 0){ return result; } int maxslong = -1;//得到字典里最长的单词的长度 for (unordered_set
          
           ::iterator it = wordDict.begin(); it != wordDict.end(); it++){ int slong = (*it).size(); if (maxslong
           
            * carry = new vector
            
             [slen + 1];//用来保存以第i个字符作为结尾的所有单词 for (int i = 1; i <= slen; i++){ for (int len = maxslong; len >= 1; len--){ if (i - len<0){ continue; } string cutstr = s.substr(i - len, len); dp[i] = (dp[i - len] && (wordDict.find(cutstr) != wordDict.end())) || dp[i]; //不光dp[i-len]要为true，他下面必须要有挂的单词才能给carry[i]继续挂单词 if ((carry[i-len].size()>0||i-len==0) && (wordDict.find(cutstr) != wordDict.end())){ carry[i].push_back(cutstr);//将这个单词挂在carry[i]下 } } } if (dp[slen] == false){//无解的情况 return result; } vector
             
               tt; dfsLoadResult(slen, carry, tt); delete[] dp; delete[] carry; return result;}