字符串的包含
博客专区 > htq 的博客 > 博客详情
字符串的包含
htq 发表于1年前
字符串的包含
  • 发表于 1年前
  • 阅读 2
  • 收藏 0
  • 点赞 0
  • 评论 0

标题:腾讯云 新注册用户域名抢购1元起>>>   

要求:给定一个主串X和子串Y判断主串是否包含子串,包含是指子串中的所用字符均在主串中出现,所谓出现不要求连续,如:主串X:abcdef  子串为:Y:cde,Z:ade,M:adx,则答案为true,true false,要求空间复杂度为O(1)

注意字符串的包含与字符串的查找的不同,具体可以参考我的博客: 字符串的查找

思路:因为是字符串的处理且要求空间复杂度为O(1),所以自然想到用哈希表处理,先扫描长串,然后用hash对长串中出现的字符进行标记,标记为1,接着在短串种扫描看对应的hash表中值是否为1,若存在一个不为1,则输出false,否则,输出ture。

基于此思路代码如下:
#include<iostream>
using namespace std;
void main()
{
    string X="ABCDEF";
	string Y="CDE";
	int hash[26]={0};
	for(int i=0;i<X.length();i++)
	{
		if(hash[X[i]-'A']==0)
			hash[X[i]-'A']=1;
	}
	for(int i=0;i<Y.length();i++)
	{
		if(hash[Y[i]-'A']==0)
		{
			cout<<"false"<<endl;
			return ;
		}
	}
	cout<<"true"<<endl;
}
程序运行结果如下:
<img src="http://img.blog.csdn.net/20160310162019518" alt="" />

推广:从这道题可以推广为,在一个字符串中查找第一个只出现一次的字符。只需将hash表中的值进行累加操作即可,hash表中第一个值为1的即为第一次出现一次的字符。



共有 人打赏支持
htq
粉丝 17
博文 67
码字总数 1007
作品 3
×
htq
如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
* 金额(元)
¥1 ¥5 ¥10 ¥20 其他金额
打赏人
留言
* 支付类型
微信扫码支付
打赏金额:
已支付成功
打赏金额: