`
jiagou
  • 浏览: 2516739 次
文章分类
社区版块
存档分类
最新评论

字符串包含问题

 
阅读更多

本题以及其他的一些题,来自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,等等。现在我遍历第一个字串,把每个字母代表的素数相乘。你最终会得到一个很大的整数,对吧? 然后——轮询第二个字符串,用每个字母除它。如果除的结果有余数,这说明有不匹配的字母。如果整个过程中没有余数,你应该知道它是第一个字串恰好的子集了。

具体实现由于时间关系,就不说了。感兴趣的,自己实现一下。

分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics