Posted on 2014-01-14 03:10
Uriel 閱讀(175)
評論(0) 編輯 收藏 引用 所屬分類:
LeetCode
問單詞串s是否可以由若干單詞相連而成（可以重復使用），這題只要判是否可以組成，簡單DP即可
1 class Solution {
2 public:
3 int dp[100010];
4 bool wordBreak(string s, unordered_set<string> &dict) {
5 int i, j;
6 memset(dp, -1, sizeof(dp));
7 dp[0] = 0;
8 unordered_set<string>::iterator it;
9 for(i = 0; i <= s.length(); ++i) {
10 for(j = 0, it = dict.begin(); it != dict.end(); ++it, ++j) {
11 int ll = it->size();
12 if(dp[i] >= 0 && i + ll <= s.length() && s.substr(i, ll) == *it) {
13 dp[i + ll] = j;
14 }
15 }
16 }
17 if(~dp[s.length()]) return true;
18 return false;
19 }
20 };