Leetcode 139 - Word Break（線性dp）

2019-11-11 04:05:01

字體：大中小

來源：轉載

供稿：網友

題意

給一個字符串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]; }};

上一篇：產生區間隨機數

下一篇：【Codeforces 724 D Dense Subsequence】+ 貪心