专栏首页算法修养LeetCode 140 Word Break II

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; } } } } } };

```

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • LeetCode 30 Substring with Concatenation of All Words

    ShenduCC
  • LeetCode Contest 179

    题解:遍历数组,维护一个最大值,当最大值等于当前的下标+1的时候,就是blue的时候

    ShenduCC
  • LeetCode 354 Russian Doll Envelopes (动态规划)

    一道好题目,把最长递增子序列扩展到二维,但是这道题和最长递增子序列是有区别的,它不要求是序列,只是在数组中找到一组最长的组合,不要求顺序在初始中相同。

    ShenduCC
  • Longest Word in Dictionary through Deleting

    Tyan
  • LeetCode 第 23 场双周赛(970/2044,前47.5%)

    做出来了 1、3 两题,继续加油! 第二道字符串的题,又是看错题,以后要多读几遍题目,题目说要使用所有字符,我视而不见,去排列组合。。。 第四题,想到了贪心...

    Michael阿明
  • C++实现字符串的分割和替换

    代码主要说明: (1)tmp.find(target):查找子串第一次出现的下标; (2)string::npos:表示未查找到子串时返回的数值。MSD...

    Dabelv
  • LeetCode 30 Substring with Concatenation of All Words

    ShenduCC
  • [干货来袭]C#7.0新特性(VS2017可用)

    前言 微软昨天发布了新的VS 2017 ..随之而来的还有很多很多东西... .NET新版本 ASP.NET新版本...等等..太多..实在没消化.. 分享一下...

    GuZhenYin
  • 堆排序

    大学里的混子
  • JNI所需的C语言知识小结

    用户1665735

扫码关注云+社区

领取腾讯云代金券