Leetcode 139 - Word Break（线性dp）

2019-11-11 05:32:39

字体：大中小

来源：转载

供稿：网友

题意

给一个字符串S和一个字典WordDict，要求判断是否能用wordDict内的数组成S。

思路

算法1

区间dp，时间复杂度O(n3) $O(n^3)$

首先将wordDict内的字符串全部丢到unordered_set<string> has里面，方便查看有没有。

状态表示：d[i,j] $d[i, j]$ ，区间s[i, j]能否用has内的字符串表示。

转移方程：d[i,j]=d[i,k]&&d[k+1,j] $d[i, j] = d[i, k] /& /& d[k + 1, j]$

算法2

线性dp，时间复杂度O(n2) $O(n^2)$

状态表示：d[i] $d[i]$ ，区间s[0, i]能够用has内的字符串表示。

转移方程：

s[0,i] $s[0, i]$ 能用has表示：d[i]=1 $d[i] = 1$ s[j+1,i]能用has内的字符串表示且d[j]==1 $s[j + 1, i]能用has内的字符串表示且d[j] == 1$ ：d[i]=1 $d[i] = 1$ 其他情况：d[i]=0 $d[i] = 0$

代码

//n^3 dpconst int maxn = 1005;class Solution {public: unordered_map<string, int> has; int d[maxn][maxn]; int dfs(int i, int j, string s) { if (i > j) return 0; if (d[i][j] != -1) return d[i][j]; if (has.find(s.substr(i, j - i + 1)) != has.end()) return d[i][j] = 1; d[i][j] = 0; for (int k = i; k < j; k++) { int t1 = dfs(i, k, s), t2 = dfs(k + 1, j, s); if (t1 == 1 && t2 == 1) d[i][j] = 1; else d[i][j] = 0; if (d[i][j] == 1) { return d[i][j]; } } return d[i][j]; } bool wordBreak(string s, vector<string>& wordDict) { if (wordDict.size() == 0) return s == ""; for (auto x : wordDict) { if (has.find(x) == has.end()) has[x] = 1; } memset(d, -1, sizeof(d)); return dfs(0, s.size() - 1, s); }};//n^2 dpclass Solution {public: unordered_set<string> has; bool wordBreak(string s, vector<string>& wordDict) { if (wordDict.empty()) return s == ""; for (auto x : wordDict) has.insert(x); vector<bool> d(s.length(), 0); string t = s.substr(0, 1); d[0] = (has.find(t) == has.end() ? 0 : 1); for (int i = 1; i < s.length(); i++) { string t = s.substr(0, i + 1); if (has.find(t) != has.end()) { d[i] = true; continue; } for (int j = 0; j < i; j++) { if (d[j]) { string tt = s.substr(j + 1, i - j); if (has.find(tt) != has.end()) d[i] = true; } } } return d[s.length() - 1]; }};

上一篇：求LCA（最近公共祖先）

下一篇：点积的应用

学习交流

索泰发布一款GTX 1070 Mini迷你版本:小机

索泰发布一款GTX 1070 Mini迷你版本:小机箱大爱...

热门图片

猜你喜欢的新闻

猜你喜欢的关注