算法练习-字符串包含

练习问题来源

https://wizardforcel.gitbooks.io/the-art-of-programming-by-july/content/01.02.html

题目描述

给定两个分别由字母组成的字符串A和字符串B，字符串B的长度比字符串A短。请问，如何最快地判断字符串B中所有字母是否都在字符串A里？

为了简单起见，我们规定输入的字符串只包含大写英文字母，请实现函数bool StringContains(string &A, string &B)

比如，如果是下面两个字符串：

String 1：ABCD

String 2：BAD

答案是true，即String2里的字母在String1里也都有，或者说String2是String1的真子集。

如果是下面两个字符串：

String 1：ABCD

String 2：BCE

答案是false，因为字符串String2里的E字母不在字符串String1里。

同时，如果string1：ABCD，string 2：AA，同样返回true。

解法一

最直观也是最简单的思路是，针对string2中每一个字符，逐个与string1中每个字符比较，看它是否在String1中。假设n是字符串String1的长度，m是字符串String2的长度，那么此算法，需要O(n*m)次操作。

实现的函数代码：

bool StringContain(string &a, string &b)
{
    for (int i=0; i<b.length(); ++i)
    {
        int j;
        for (j=0; j<a.length(); ++j)
        {
            if (b[i] == a[j])
            {
                break;
            }
        }
        if(j >= a.length())
            return false;
    }
    return true;
}

解法二

如果允许排序的话，我们可以考虑下排序。比如可先对这两个字符串的字母进行排序，然后再同时对两个字串依次轮询。两个字串的排序需要(常规情况)O(m log m) + O(n log n)次操作，之后的线性扫描需要O(m+n)次操作。

实现的函数代码如下：

void qsort(string &a, int l, int r)
{
    int i, j;
    char c;
    if(l < r)
    {
        i = l;
        j = r;
        c = a[i];
        while(i < j)
        {
            // 从右向左找第一个小于 c 的字符
            while(i < j && a[j] > c)
                --j;
            if(i < j)
                a[i++] = a[j];
            // 从左向右找第一个大于 c 的字符
            while(i < j && a[i] < c)
                ++i;
            if(i < j)
                a[j--] = a[i];
        }
        a[i] = c;
        qsort(a, l, i-1);
        qsort(a, i+1, r);
    }
}

bool StringContain_Sort(string &a, string &b)
{
    qsort(a, 0, a.length()-1);
    qsort(b, 0, b.length()-1);
    for (int ai = 0, bj = 0; bj < b.length();)
    {
        while(ai < a.length() && a[ai] < b[bj])
        {
            ++ai;
        }
        if (a[ai] == b[bj])
        {
            ++bj;
        }
        else
            return false;
    }
    return true;
}

解法三

事实上，可以先把长字符串a中的所有字符都放入一个Hashtable里，然后轮询短字符串b，看短字符串b的每个字符是否都在Hashtable里，如果都存在，说明长字符串a包含短字符串b，否则，说明不包含。

再进一步，我们可以对字符串A，用位运算（26bit整数表示)计算出一个“签名”，再用B中的字符到A里面进行查找。

这个方法的实质是用一个整数代替了hashtable，空间复杂度为O(1)，时间复杂度还是O(n + m)

实现的函数代码如下：（有些问题，结果不正确）

bool StringContain_Hash(string &a, string &b)
{
    int hash = 0;
    for (int i = 0; i < a.length(); ++i)
    {
        hash |= (1 << (a[i] - 'A'));
    }
    for (int j = 0; j < b.length(); ++j)
    {
        if ((hash &= (1 << (b[j] - 'A'))) == 0)
        {
            return false;
        }
    }
    return true;
}

对函数测试部分的文件：

  1 #include <string>
  2 #include <cstdlib>
  3 #include <iostream>
  4 
  5 using namespace std;
  6 bool StringContain(string &a, string &b)
  7 {
  8     for (int i=0; i<b.length(); ++i)
  9     {
 10         int j;
 11         for (j=0; j<a.length(); ++j)
 12         {
 13             if (b[i] == a[j])
 14             {
 15                 break;
 16             }
 17         }
 18         if(j >= a.length())
 19             return false;
 20     }
 21     return true;
 22 }
 23 void qsort(string &a, int l, int r)
 24 {
 25     int i, j;
 26     char c;
 27     if(l < r)
 28     {
 29         i = l;
 30         j = r;
 31         c = a[i];
 32         while(i < j)
 33         {
 34             // 从右向左找第一个小于 c 的字符
 35             while(i < j && a[j] > c)
 36                 --j;
 37             if(i < j)
 38                 a[i++] = a[j];
 39             // 从左向右找第一个大于 c 的字符
 40             while(i < j && a[i] < c)
 41                 ++i;
 42             if(i < j)
 43                 a[j--] = a[i];
 44         }
 45         a[i] = c;
 46         qsort(a, l, i-1);
 47         qsort(a, i+1, r);
 48     }
 49 }
 50 bool StringContain_Sort(string &a, string &b)
 51 {
 52     qsort(a, 0, a.length()-1);
 53     qsort(b, 0, b.length()-1);
 54     for (int ai = 0, bj = 0; bj < b.length();)
 55     {
 56         while(ai < a.length() && a[ai] < b[bj])
 57         {
 58             ++ai;
 59         }
 60         if (a[ai] == b[bj])
 61         {
 62             ++bj;
 63         }
 64         else
 65             return false;
 66     }
 67     return true;
 68 }
 69 bool StringContain_Hash(string &a, string &b)
 70 {
 71     int hash = 0;
 72     for (int i = 0; i < a.length(); ++i)
 73     {
 74         hash |= (1 << (a[i] - 'A'));
 75     }
 76     for (int j = 0; j < b.length(); ++j)
 77     {
 78         if ((hash &= (1 << (b[j] - 'A'))) == 0)
 79         {
 80             return false;
 81         }
 82     }
 83     return true;
 84 }
 85 
 86 void main()
 87 {
 88     string a = "TIHS";
 89     string b = "SIA";
 90     cout << "a = " << a << endl;
 91     cout << "b = " << b << endl;
 92     if(StringContain_Sort(a, b))
 93         cout << "true" << endl;
 94     else
 95         cout << "false" << endl;
 96 /*  // 测试快排算法
 97     string sd = "DFCAEBdad";
 98     qsort(sd, 0, sd.length()-1);
 99     cout << sd <<endl;*/
100 }

字符串包含的测试 mian() 函数