注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

HT·生活

123

 
 
 

日志

 
 

ex139 Word Break  

2015-05-20 22:54:08|  分类: leetcode |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
就是根据字典将给定字符串break出来

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".

我开始用的是暴力遍历字典的方法,大集合肯定过不去,不过代码还是贴一下

bool wordBreak1(string s, unordered_set<string>& wordDict) {

unordered_set<string>::iterator it;
string temp,str,pre_str;
int index = 0;
str = s;
//这个方法比较暴力,从s的第一个字符开始匹配,先找s[0]在wordDict的匹配
//然后擦除,如果最终没有匹配的话,重置str,这个方法其实是丢弃了以前匹配的有用信息
do
{
pre_str = str;
for (it = wordDict.begin(); it != wordDict.end(); it++)
{
temp = *it;
if (temp[0] == str[0])
{
index = str.find(*it);
while (index >= 0)
{
str.erase(index,temp.size());
if (str.empty())
{
return true;
}
index = s.find(temp);
}
}
}
if (pre_str == str)
break;
} while (!str.empty());
return false;

后来参考了别人的思路,还是动态规划的思想,就是从前往后遍历字符串,开一个数组dp,然后dp[i]表示当前的字符前面0-i能否被break,一直往后递推。见c代码

class Solution {
public:
bool wordBreak(string s, unordered_set<string>& wordDict) {
/*
* 网上推荐的都是用的dp规划的算法,不过仔细想想也是
* 先看第一个字符有没有被匹配,然后查看0-1字符是否匹配,然后一直到到s的最后
* 滚动计算结果
*/
unordered_set<string>::iterator it;
string str;
int i,index = 0;
int nsize = s.size();
bool *dp = new bool[nsize];

for (i = 0; i < nsize; i++)
{
dp[i] = false; //初始化一下

dp[i] =(wordDict.find(s.substr(0, i + 1))==wordDict.end())?false:true;
if (!dp[i])
{
//没匹配上,再分割0->i的字符,看看是否能够匹配上
for (int j = 0; j < i; j++)
{
//从j处分割
if (dp[j])
{
//匹配j+1下标开始,总共i-j个字符
dp[i] = (wordDict.find(s.substr(j+1, i - j)) == wordDict.end()) ? false : true;
if (dp[i])
{
break;
}
}
}
}
else
{
//do nothing 因为这个已经匹配上了
}
}
bool result = dp[nsize - 1];
delete[] dp;
return result;

}
};



参考
http://www.cnblogs.com/ballwql/p/3708022.html
http://blog.csdn.net/doc_sgl/article/details/12323015
  评论这张
 
阅读(9)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017