本题以及其他的一些题,来自July的博客(http://blog.csdn.net/v_JULY_v)中,因最近正在学习,所以加一些自己的感受。
判断string2中的字符是否在string1中?:
String 1: ABCDEFGHLMNOPQRS
String 2: DCGSRQPOM
思路:
判断一个字符串是否在另一个字符串中,最直观也是最简单的思路是,针对第二个字符串string2中每一个字符,一一与第一个字符串string1中每个字符依次轮询比较,看它是否在第一个字符串string1中。
在July出来的PDF资料中,if(LongString[j] == ShortString[i])语句有问题,原题把i和j的位子倒了。在此纠正一下。
到目前为止,最原始的方法已经出来了,但貌似时间复杂度有点儿大,为O(n*m)。所以,还需要继续优化。
接下来是一种改进的方法,用数组或者是Hashtable可以将复杂度将为O(n+m);
二者原理一样:声明一个额外的数组,先遍历短字符串,把所有的字母,按顺序在数组里的相应的位置标为true.如:如果短字符串里包含
A,则在数组里,将第一个值赋为true.如果为Z,则将第26个置为true。
然后遍历长字符串,长字符串里有的,将数组里的置为false,最后遍历数组,如果依然有true,则说明长字符串没有 完全包含短字符串。
思路不好理解,最好距离自己画画图。
代码如下:
这里用到一个memset(),意思:
void *memset(void *s, int ch, size_t n);
函数解释:将s中前n个字节替换为ch并返回s;
百度百科:http://baike.baidu.com/view/982208.htm。有兴趣的去研究研究。
至此July的博客还给出了另一种思路:
假设我们有一个一定个数的字母组成字串,我给每个字母分配一个素数,从2开始,往后类推。这样A将会是2,B将会是3,C将会是5,等等。现在我遍历第一个字串,把每个字母代表的素数相乘。你最终会得到一个很大的整数,对吧? 然后——轮询第二个字符串,用每个字母除它。如果除的结果有余数,这说明有不匹配的字母。如果整个过程中没有余数,你应该知道它是第一个字串恰好的子集了。
具体实现由于时间关系,就不说了。感兴趣的,自己实现一下。
分享到:
相关推荐
第四节、字符串是否包含问题的继续补充 4.1、Bit-map 4.2、移位操作 第五节、字符串相关问题扩展 5.1、字符串匹配问题 5.2、在字符串中查找子串 扩展:在一个字符串中找到第一个只出现一次的字符 5.3、字符串...
indexOf() 方法可返回某个指定的字符串值在字符串中首次出现的位置。如果要检索的字符串值没有出现,则该方法返回 -1。 方法二:match() var str = "123" var reg = RegExp(/3/); if(str.match(reg)){ //包含; } ...
判断字符串是否包含emoji表情
编写程序:从键盘上输入一个包含10个字符的字符串,把该字符串与程序中给定的字符串("bacdbcabca") //依次比较,统计两个字符串对应字符相等的数目。然后输出从键盘上输入的字符串, //并把两个字符串中对应字符不...
使用正则表达式判断字符串中是否包含中文汉字或者中文符号
主要介绍了JavaScript判断一个字符串是否包含指定子字符串的方法,实例分析了javascript字符串操作的技巧,非常具有实用价值,需要的朋友可以参考下
//js统计字符串中包含的特定字符个数 function getPlaceholderCount(strSource) { //统计字符串中包含{}或{xxXX}的个数 var thisCount = 0; strSource.replace(/\{[xX]+\}|\{\}/g, function (m, i) { //m为找到...
对于给定任意的字符串,如何快速的判断该字符串中是否包含汉字。
用户输入一个字符串后,判断该字符串中包含几个汉字
输入一个字符串参数,返回该字符串的反序字符串
本文实例讲述了C#判断字符串是否存在字母及字符串中字符的替换的方法。分享给大家供大家参考。具体实现方法如下: 首先要添加对命名空间“using System.Text.RegularExpressions;”的引用 下面以一个字符串为例: ...
db2里对字符串处理的函数大全,涵盖常见和不常见的很多函数
必须实现如下操作,字符串比较、求串的长度、判断串是否为空、将串置空、字符串赋值(包括两个字符串类复制,一个字符串赋值到CmyString对象)、求字符串中的一个字符或改变字符串中的一个字符(采用重载[]),完成...
过滤一个字符串中包含有表情的字符,例如一个用户昵称中包含的表情
具体来说,它首先创建了一个包含3个字符串的字符串数组`strArray`,然后定义了一个新的字符串`newStr`。接着,使用`ismember()`函数检查新字符串是否已经存在于字符串数组中。如果新字符串不存在于字符串数组中,则...
查找单元格中包含特定字符串中的某一个,并返回该特定字符串,查找单元格中包含特定字符串中的某一个,并返回该特定字符串
C语言程序设计-输入一个字符串,过滤此串,只保留串中的字母字符,并统计新生成串中包含的字母个数;例如:输入的字符串为ab234$df4,新生成的串为abdf ;.c
Java 正则表达式判断字符串是否包含中文
字符串数组 matlabMATLAB字符串数组 基本规则 (1)所有字符串都用单引号(英文状态下输入)括起来; (2)将字符串当作一个行向量,每个元素对应一个字符,其标识方法和数值向量相同。 (3)size指令获得串数组的大小。串...
以下给出一些shell中判断字符串包含的方法,来源程序员问答网站 stackoverflow 以及segmentfault。 方法一:利用grep查找 strA=long string strB=string result=$(echo $strA | grep ${strB}) if [[ $result != ]] ...