Uriel's Corner

Research Associate @ Harvard University / Research Interests: Computer Vision, Biomedical Image Analysis, Machine Learning
posts - 0, comments - 50, trackbacks - 0, articles - 594

[LeetCode]Word Break-2014.01.13

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

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理