字符串包含

题目描述

给定两个分别由字母组成的字符串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里。

求解

解法1 暴力轮询

对string2中的每一个字符，逐个与string1中的每个字符比较，看它是否在string1中。
假设string1长度为n，string2长度为m，那么这个算法的时间复杂度为O(n*m)。
代码如下：

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

解法2 首先排序，利用有序性进行检验

首先对两个字符串中的字母进行排序O(mlogm)+O(nlogn)，然后进行线性扫描O(m+n)。

bool stringContain(string &a, string &b) {
    sort(a.begin(), a.end());
    sort(b.begin(), b.end());
    for (int pa = 0, pb = 0; pb < b.length();) {
        while((pa<a.length()) && (a[pa] < b[pb])) {
            pa++;
        }
        if ((pa >= a.length()) || (a[pa] > b[pb])) {
            return false;
        }
        pb++;
    }
    return true;
}

解法3 利用素数不能被其他数字整除的性质

1.按照从小到大的顺序，用26个素数分别与字符'A'到'Z'一一对应。
2.遍历长字符串，求得每个字符对应素数的乘积。
3.遍历短字符串，判断乘积能否被短字符串中的字符对应的素数整除。
4.输出结果。
时间复杂度为O(m+n)

bool stringContain(string &a, string &b) {
    const int p[26] = {2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101};
    int f = 1;
    for (int i = 0; i < a.length(); i++) {
        int tmp = p[ a[ i ] - 'a' ];
        if (f % tmp) {
            f *= tmp;
        }
    }
    for (int i = 0; i < b.length(); i++) {
        int tmp = p[ b[ i ] - 'a' ];
        if (f % tmp) {
            return false;
        }
    }
    return true;
}

解法4

可以使用hash完成，首先对长字符串进行轮询，放入hash，然后对短字符串进行轮询，如果hash中没有则返回失败。如果全都有则成功。
这里由于只有26bit所以使用一个int代替hash。空间复杂度为O(1)。时间复杂度为O(m+n)。

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

总的测试程序如下：

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
bool stringContain0(string &a, string &b);
bool stringContain1(string &a, string &b);
bool stringContain2(string &a, string &b);
bool stringContain3(string &a, string &b);
int main(void) {
    string a = "fqwer";
    string b = "rewq";
    bool c = stringContain0(a, b);
    cout << c << endl;
    c = stringContain1(a, b);
    cout << c << endl;
    c = stringContain2(a, b);
    cout << c << endl;
    c = stringContain3(a, b);
    cout << c << endl;
}
bool stringContain0(string &a, string &b) {
    for(int i = 0; i < b.length(); i++) {
        int j;
        for(j = 0; (j < a.length() && a[j] != b[i]); j++)
            ;
        if (j >= a.length())
            return false;
    }
    return true;
}
bool stringContain1(string &a, string &b) {
    sort(a.begin(), a.end());
    sort(b.begin(), b.end());
    for (int pa = 0, pb = 0; pb < b.length();) {
        while((pa<a.length()) && (a[pa] < b[pb])) {
            pa++;
        }
        if ((pa >= a.length()) || (a[pa] > b[pb])) {
            return false;
        }
        pb++;
    }
    return true;
}
bool stringContain2(string &a, string &b) {
    const int p[26] = {2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101};
    int f = 1;
    for (int i = 0; i < a.length(); i++) {
        int tmp = p[ a[ i ] - 'a' ];
        if (f % tmp) {
            f *= tmp;
        }
    }
    for (int i = 0; i < b.length(); i++) {
        int tmp = p[ b[ i ] - 'a' ];
        if (f % tmp) {
            return false;
        }
    }
    return true;
}

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