[算法] 字符串包含


#1

题目描述

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

分析与解法

最直接了当的做法当然是拿 B 中的每一个字符分别去和 A 中的字符顺序进行比较。假设 B 的字符串长度为 m,A 的字符串长度为 n,则时间复杂度为 O(m*n) ,显然不满足题目中要求的最快的方式。

考虑题目要求时间复杂度尽可能快,我们尝试用空间来换时间。因为 A 中最多包含26个大写英文字母,我们可以针对 A 构造一个包含 26 个节点的二叉查找树。构造过程需要 O(nlogn) 的时间复杂度和 O(logn) 的空间复杂度。查找的过程需要 O(logm) 的时间复杂度,综合起来相当于 O(nlogn) + O(logm) 的时间复杂度。

那么还有没有更快的方式呢?可以使用位运算。我们可以把 A 中的每个字母从 AZ 进行编码放入一个 26 个 bit 的整数中,字母所在字母表中的序号是几,那么这 26 个 bit 中的第几个 bit 就是 1,否则这一位是 0。这样的话,再用 B 中所含每一个字母所在位置编码同 A 所得的编码进行按位与操作,即可得知 B 中每一个字母是否都在 A 中存在。代码如下:

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;
}

此方法空间复杂度为O(1),时间复杂度为O(n + m)。