首页 > 其他 > 详细

分词问题分析

时间:2014-07-10 21:44:20      阅读:439      评论:0      收藏:0      [点我收藏+]

题目来源,待字闺中,原创@陈利人 ,欢迎大家继续关注微信公众账号“待字闺中”

给定字符串,以及一个字典,判断字符串是否能够拆分为字段中的单词。例如,字段为{hello,world},字符串为hellohelloworld,则可以拆分为hello,hello,world,都是字典中的单词。

思想:最直接的思路就是递归,我们考虑每一个前缀,是否在字典中?如果在,则递归处理剩下的字串;如果不再,则考虑下一个前缀。写成表达式就是fun(i)=substr(i,j-i+1) && fun(j+1),其中i<=j<n-1,且substr(i,j-i+1)在字典中。很显然,该递归包含很多重复子问题,所以可以用动态规划,状态转移方程和上面类似,加速的原因是我们只计算一次子问题,即从后向前计算dp[i]=substr(s,j-i+1) && dp[j+1],具体代码如下:

bool dictionaryContain(const set<string>& strset,const string& str)
{
	set<string>::iterator iter = strset.find(str);
	if(iter != strset.end())return true;
	else return false;
}

bool wordBreak(const string& str,const set<string>& strset)
{
	int length = str.size();
	bool* dp = new bool[length+1];
	memset(dp,0,sizeof(bool)*(length+1));
	dp[length] = true;
	int i,j;
	for(i=length-1;i>=0;i--)//从后向前计算dp
	{
		for(j=i;j<=length;j++)
		{
			if(dictionaryContain(strset,str.substr(i,j-i+1)) && dp[j+1])//状态转移方程
			{
				dp[i] = true;
				break;
			}
		}
	}
	return dp[0];
}

以上只代表个人想法,如果有问题,请指出,谢谢

分词问题分析,布布扣,bubuko.com

分词问题分析

原文:http://blog.csdn.net/fangjian1204/article/details/37655195

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!