文档章节

字符串的包含

htq
 htq
发布于 2016/07/26 09:41
字数 366
阅读 3
收藏 0
点赞 0
评论 0

要求:给定一个主串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的即为第一次出现一次的字符。



本文转载自:http://blog.csdn.net/htq__/article/details/50847668

共有 人打赏支持
htq

htq

粉丝 19
博文 67
码字总数 1007
作品 3
武汉
PHP 正则——一些常用的特殊字符。

p+ 匹配任何一个至少包含p的字符串 p* 匹配任何包含零个或多个p的字符串 p? 匹配任何包含零个或一个P的字符串 可选(类似) p{2} 匹配任何包含两个P序列的字符串 p{2,3} 匹配任何包含两个或三个...

virhuiai ⋅ 2013/03/25 ⋅ 0

Swift3.0语言教程查找字符集和子字符串

Swift3.0语言教程查找字符集和子字符串 Swift3.0语言教程查找字符集和子字符串,在字符串中当字符内容很多时,我们就需要使用到查找字符集或者子字符串的方法。以下我们将讲解3种查找字符集和...

大学霸 ⋅ 2016/11/11 ⋅ 1

如何在 Linux shell 中找出所有包含指定文本的文件

目标:本文提供一些关于如何搜索出指定目录或整个文件系统中那些包含指定单词或字符串的文件。 难度:容易 约定: - 需要使用 root 权限来执行指定命令,可以直接使用 root 用户来执行也可以...

作者: Lubos Rendek ⋅ 2017/12/18 ⋅ 0

PHP验证时常用到的函数

检查变量是否是数字或数字式字符串: $success = is_numeric($string); 如果变量是数字,或者是包含数字及符号、小数点、指数的字符串,这个函数就会返回True。 完整文档:http://php.net/is...

ccxj520 ⋅ 2013/07/12 ⋅ 0

字符串的小方法

本博文包含upper()、lower()、isupper()、islower()、isX、startswith()、endswith()、join()、split()、 upper(),lower():将字符串中所有字母转化为大写和小写,其他字符不变。isupper(),i...

v_fanyunxiao ⋅ 2017/08/24 ⋅ 0

RandomStringUtils的说明和生成随机汉字

这类位于 org.apache.commons.lang。 简单说一下都有哪些方法(具体参考源码文件): random(int count) 生成一个长度为count的字符串,随机内容包含全部的编码。 randomAscii(int count) 生...

登琼 ⋅ 2016/04/20 ⋅ 0

Sql Server中常用的字符串函数

len(expression) 返回给定字符串表达式的字符(而不是字节)个数,其中不包含尾随空格。 datalength(Char_expr)返回字符串包含字符数,但不包含后面的空格 length(expression,variable)指定字...

学习也休闲 ⋅ 2015/09/23 ⋅ 0

python学习笔记五:字符串方法

常用字符串常量: string.digits:包含数字0~9的字符串 string.letters:包含所有字母(大写或小写字符串,在python3.0中,使用string.ascii-letters代替) string.lowercase:包含所有小写字...

笑看天空 ⋅ 2017/04/19 ⋅ 0

SQL--mysql正则与like

1.like 匹配字符的作用 1.1%:通配符,表示任何字符(除了null外)出现任意次数。例如: 1.like '%zg',匹配以zg结尾的所有字符串2.like 'zg%',匹配以zg开头的所有字符串 3.like '%zg%',匹配...

求是科技 ⋅ 2016/10/10 ⋅ 0

swift 中String常用操作

字符串定义 var s = "aaaaaa" // 两个字符串均为空并等价。var emptyString = "" var anotherEmptyString = String() 字符串字面量可以包含以下特殊字符:转义字符 (空字符)、 (反斜线)、 (水...

我是IT码农 ⋅ 2015/08/28 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

来自一个优秀Java工程师的简历

写在前面: 鉴于前几天的一份前端简历,虽然带着很多不看好的声音,但却帮助了很多正在求职路上的人,不管评论怎么说,我还是决定要贴出一份后端的简历。 XXX ID:357912485 目前正在找工作 ...

颖伙虫 ⋅ 21分钟前 ⋅ 0

Confluence 6 恢复一个站点有关使用站点导出为备份的说明

推荐使用生产备份策略。我们推荐你针对你的生产环境中使用的 Confluence 参考 Production Backup Strategy 页面中的内容进行备份和恢复(这个需要你备份你的数据库和 home 目录)。XML 导出备...

honeymose ⋅ 今天 ⋅ 0

JavaScript零基础入门——(九)JavaScript的函数

JavaScript零基础入门——(九)JavaScript的函数 欢迎回到我们的JavaScript零基础入门,上一节课我们了解了有关JS中数组的相关知识点,不知道大家有没有自己去敲一敲,消化一下?这一节课,...

JandenMa ⋅ 今天 ⋅ 0

火狐浏览器各版本下载及插件httprequest

各版本下载地址:http://ftp.mozilla.org/pub/mozilla.org//firefox/releases/ httprequest插件截至57版本可用

xiaoge2016 ⋅ 今天 ⋅ 0

Docker系列教程28-实战:使用Docker Compose运行ELK

原文:http://www.itmuch.com/docker/28-docker-compose-in-action-elk/,转载请说明出处。 ElasticSearch【存储】 Logtash【日志聚合器】 Kibana【界面】 答案: version: '2'services: ...

周立_ITMuch ⋅ 今天 ⋅ 0

使用快嘉sdkg极速搭建接口模拟系统

在具体项目研发过程中,一旦前后端双方约定好接口,前端和app同事就会希望后台同事可以尽快提供可供对接的接口方便调试,而对后台同事来说定好接口还仅是个开始、设计流程,实现业务逻辑,编...

fastjrun ⋅ 今天 ⋅ 0

PXE/KickStart 无人值守安装

导言 作为中小公司的运维,经常会遇到一些机械式的重复工作,例如:有时公司同时上线几十甚至上百台服务器,而且需要我们在短时间内完成系统安装。 常规的办法有什么? 光盘安装系统 ===> 一...

kangvcar ⋅ 昨天 ⋅ 0

使用Puppeteer撸一个爬虫

Puppeteer是什么 puppeteer是谷歌chrome团队官方开发的一个无界面(Headless)chrome工具。Chrome Headless将成为web应用自动化测试的行业标杆。所以我们很有必要来了解一下它。所谓的无头浏...

小草先森 ⋅ 昨天 ⋅ 0

Java Done Right

* 表示难度较大或理论性较强。 ** 表示难度更大或理论性更强。 【Java语言本身】 基础语法,面向对象,顺序编程,并发编程,网络编程,泛型,注解,lambda(Java8),module(Java9),var(...

风华神使 ⋅ 昨天 ⋅ 0

Linux系统日志

linux 系统日志 /var/log/messages /etc/logrotate.conf 日志切割配置文件 https://my.oschina.net/u/2000675/blog/908189 logrotate 使用详解 dmesg 命令 /var/log/dmesg 日志 last命令,调......

Linux学习笔记 ⋅ 昨天 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部