Posted on 2014-01-14 03:10
Uriel 阅读(139)
评论(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 };