題意
給一個(gè)字符串S和一個(gè)字典WordDict，要求判斷是否能用wordDict內(nèi)的數(shù)組成S。
思路
算法1
區(qū)間dp，時(shí)間復(fù)雜度O(n3)
首先將wordDict內(nèi)的字符串全部丟到unordered_set<string> has里面，方便查看有沒(méi)有。
狀態(tài)表示：d[i,j]，區(qū)間s[i, j]能否用has內(nèi)的字符串表示。
轉(zhuǎn)移方程：d[i,j]=d[i,k]&&d[k+1,j]
算法2
線(xiàn)性dp，時(shí)間復(fù)雜度O(n2)
狀態(tài)表示：d[i]，區(qū)間s[0, i]能夠用has內(nèi)的字符串表示。
轉(zhuǎn)移方程：
s[0,i]能用has表示：d[i]=1s[j+1,i]能用has內(nèi)的字符串表示且d[j]==1：d[i]=1其他情況：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]; }};
