首页 > 程序开发 > 软件开发 > C语言 >

程序员编程艺术:第二章、字符串是否包含及相关问题扩展

2011-06-16

前奏     前一章,请见这:程序员面试题狂想曲:第一章、左旋转字符串。本章里出现的所有代码及所有思路的实现,在此之前,整个网上都是没有的。     文中的思路,聪明点点的都能想到,巧的思路,大师也

前奏

前一章,请见这:程序员面试题狂想曲:第一章、左旋转字符串。本章里出现的所有代码及所有思路的实现,在此之前,整个网上都是没有的。

文中的思路,聪明点点的都能想到,巧的思路,大师也已奉献了。如果你有更好的思路,欢迎提供。如果你对此狂想曲系列有任何建议,欢迎微博上交流或来信指导。任何人,有任何问题,欢迎随时不吝指正。

如果此狂想曲系列对你有所帮助,我会非常之高兴,并将让我有了永久坚持写下去的动力。谢谢。


第一节、一道俩个字符串是否包含的问题
1.0、题目描述:
假设这有一个各种字母组成的字符串,假设这还有另外一个字符串,而且这个字符串里的字母数相对少一些。从算法是讲,什么方法能最快的查出所有小字符串里的字母在大字符串里都有?

比如,如果是下面两个字符串:
String 1: ABCDEFGHLMNOPQRS
String 2: DCGSRQPOM
答案是true,所有在string2里的字母string1也都有。

如果是下面两个字符串:
String 1: ABCDEFGHLMNOPQRS
String 2: DCGSRQPOZ
答案是false,因为第二个字符串里的Z字母不在第一个字符串里。

点评:
1、题目描述虽长,但题意简单明了,就是给定一长一短的俩个字符串A,B,假设A长B短,现在,要你判断B是否包含在字符串A中,即B?(-A。

2、题意虽简单,但实现起来并不轻松,且当如果面试官步步紧逼,一个一个否决你能想到的方法,要你给出更好、最好的方案时,你恐怕就要伤不少脑筋了。

ok,在继续往下阅读之前,您最好先想个几分钟,看你能想到的最好方案是什么,是否与本文最后实现的方法一致。


1.1、O(n*m)的轮询方法

判断string2中的字符是否在string1中?:
String 1: ABCDEFGHLMNOPQRS
String 2: DCGSRQPOM

判断一个字符串是否在另一个字符串中,最直观也是最简单的思路是,针对第二个字符串string2中每一个字符,一一与第一个字符串string1中每个字符依次轮询比较,看它是否在第一个字符串string1中。

假设n是字符串string1的长度,m是字符串string2的长度,那么此算法,需要O(n*m)次操作,拿上面的例子来说,最坏的情况下将会有16*8 = 128次操作。

我们不难写出以下代码:

view plaincopy to clipboardprint?
#include <iostream>
using namespace std;

int compare(string str1,string str2)
{
for (int i=0; i<str2.length(); i++)
{
for (int j=0; j<str1.length(); j++) //O(n*m)
{
if (str2[i] == str1[j]) //一一比较
{
break;
}

}
if (j==str1.length())
{
cout << "false" << endl;
return 0;
}
}
cout << "true" << endl;
return 1;
}

int main()
{
string str1="ABCDEFGHLMNOPQRS";
string str2="DCGSRQPOM";
compare(str1,str2);
return 0;
}

上述代码的时间复杂度为O(n*m),显然,时间开销太大,我们需要找到一种更好的办法。

1.2、O(mlogm)+O(nlogn)+O(m+n)的排序方法
一个稍微好一点的方案是先对这两个字符串的字母进行排序,然后同时对两个字串依次轮询。两个字串的排序需要(常规情况)O(m log m) + O(n log n)次操作,之后的线性扫描需要O(m+n)次操作。

同样拿上面的字串做例子,将会需要16*4 + 8*3 = 88加上对两个字串线性扫描的16 + 8 = 24的操作。(随着字串长度的增长,你会发现这个算法的效果会越来越好)

关于采用何种排序方法,我们采用最常用的快速排序,下面的快速排序的代码用的是以前写的,比较好懂,并且,我执意不用库函数的qsort代码。唯一的问题是,此前写的代码是针对整数进行排序的,不过,难不倒我们,稍微改一下参数,即可,如下:

view plaincopy to clipboardprint?
//copyright@ 2011 July && yansha
//July,updated,2011.04.23.
#include <iostream>
#include <string>
using namespace std;

//以前的注释,还让它保留着
int partition(string &str,int lo,int hi)
{
int key = str[hi]; //以最后一个元素,data[hi]为主元
int i = lo - 1;
for(int j = lo; j < hi; j++) ///注,j从p指向的是r-1,不是r。
{
if(str[j] <= key)
{
i++;
swap(str[i], str[j]);
}
}
swap(str[i+1], str[hi]); //不能改为swap(&data[i+1],&key)
return i + 1;
}

//递归调用上述partition过程,完成排序。
void quicksort(string &str, int lo, int hi)
{
if (lo < hi)
{
int k = partition(str, lo, hi);
quicksort(str, lo, k - 1);
quicksort(str, k + 1, hi);
}
}

//比较,上述排序O(m log m) + O(n log n),加上下面的O(m+n),
//时间复杂度总计为:O(mlogm)+O(nlogn)+O(m+n)。
void compare(string str1,string str2)
{
int posOne = 0;
int posTwo = 0;
while (posTwo < str2.length() && posOne < str1.length())
{
while (str1[posOne] < str2[posTwo] && posOne < str1.length() - 1)
posOne++;
//如果和str2相等,那就不能动。只有比str2小,才能动。

if (str1[posOne] != str2[posTwo])
break;

//posOne++;
//归并的时候,str1[str1Pos] == str[str2Pos]的时候,只能str2Pos++,str1Pos不可以自增。
//多谢helloword指正。

posTwo++;
}

if (posTwo == str2.length())
cout << "t

相关文章
最新文章
热点推荐