频道栏目
首页 > 程序开发 > 软件开发 > C语言 > 正文
程序员编程艺术:第二章、字符串是否包含及相关问题扩展
2011-06-16 10:18:50           
收藏   我要投稿

前奏

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

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

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


第一节、一道俩个字符串是否包含的问题
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

点击复制链接 与好友分享!回本站首页
上一篇:程序员编程艺术(算法卷):第一章、左旋转字符串
下一篇:程序员编程艺术:第三章、寻找最小的k个数
相关文章
图文推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站