Chinaunix首页 | 论坛 | 博客
  • 博客访问: 122005
  • 博文数量: 53
  • 博客积分: 0
  • 博客等级: 民兵
  • 技术积分: 620
  • 用 户 组: 普通用户
  • 注册时间: 2014-08-24 16:22
文章存档

2014年(53)

我的朋友

分类: C/C++

2014-09-22 18:14:57

Given a string s and a dictionary of words dict, determine if s can be segmented into a space-separated sequence of one or more dictionary words.

For example, given
s = "leetcode",
dict = ["leet", "code"].

Return true because "leetcode" can be segmented as "leet code".


Have you been asked this question in an interview?

此题相当简单,动态规划

  1. bool wordBreak(string s, unordered_set<string> &dict) {
  2.         int len=s.length();
  3.         vector<bool> dp(len+1,false);
  4.         dp[0]=true;
  5.         for(int i=0;i<=len;i++){
  6.             for(int j=0;j<i;j++){
  7.                 if(dict.find(s.substr(j,i-j))!=dict.end() && dp[j]==true){
  8.                     dp[i]=true;
  9.                 }
  10.             }
  11.         }
  12.         return dp[len];
  13.     }

阅读(993) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~