LeetCode 140 Word Break II

[LeetCode 140. Word Break II](https://leetcode.com/problems/word-break-ii/description/)

在上一道的动态规划的基础上，使用DFS打印路径。

在DFS的过程，需要记录下路径，这样就不会超时了。

100ms 已经算是个一个很差的解法了。

c++

```

class Solution { public: map<string,int> m; map<string,int> m2; int dp[505][505]; int dp2[505][505]; string sb; vector<string> vis[505][505]; vector<string> wordBreak(string s, vector<string>& wordDict) { for(int i=0;i<wordDict.size();i++) m[wordDict[i]]=1; memset(dp,0,sizeof(dp)); fun(s); sb=s; vector<string> ans; if(dp[0][sb.size()-1]==0) return ans ; return dfs(sb,0,sb.size()-1); } vector<string> dfs(string s,int l,int r) { vector<string> ss; vector<string> ss2; if(dp2[l][r]==1) ss.push_back(s); for(int i=l;i<r;i++) { if(dp[l][i]==1&&dp[i+1][r]==1) { vector<string> s1; vector<string> s2; if(vis[l][i].size()!=0) s1=vis[l][i]; else s1=dfs(sb.substr(l,i-l+1),l,i); if(vis[i+1][r].size()!=0) s2=vis[i+1][r]; else s2=dfs(sb.substr(i+1,r-i),i+1,r); for(int j=0;j<s1.size();j++) { for(int k=0;k<s2.size();k++) { ss.push_back(s1[j]+" "+s2[k]); } } } } m2.clear(); for(int i=0;i<ss.size();i++) { if(m2[ss[i]]==1) continue; m2[ss[i]]=1; ss2.push_back(ss[i]); } vis[l][r]=ss2; return ss2; } void fun(string s) { int len=s.length(); for(int l=1;l<=len;l++) { for(int i=0;i+l-1<len;i++) { int j=i+l-1; string s1 = s.substr(i,l); if(m[s1]==1) { dp[i][j]=1;dp2[i][j]=1;} else{ for(int k=i;k<j;k++) { if((dp[i][k]==1||dp[i][k]==2)&&(dp[k+1][j]==1||dp[k+1][j]==2)) dp[i][j]=1; } } } } } };

```