字符串包含判断

问题描述

给定两个字符串L1和L2,如何快速地判断字符串L2中所有字母是否都在字符串L1中。假设字符全都是大写字母。

分析与解法

这道题就是集合包含关系的判断,子不过全集是所有的大写字母。

解法一 哈希

很容易想到用哈希来解这道题,字符串用哈希非常方便,自己定义一个数组就行。时间复杂度是O(m+n)。

更进一步,由于只需要判断字符是否存在,每一个字符只需要二进制的一位来表示,可以节省空间。实现的话可以用C++的bitset或者自己用位运算实现。下面会给出用位运算实现的代码,只需要一个整数的空间。

// “最好的方法”,时间复杂度O(n + m),空间复杂度O(1)
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;
}

解法二:素数映射

这是一种很巧妙的方法。将每一个字母与一个素数对应,遍历第一个字符串,一次将对应的素数相乘,会得到一个整数。然后遍历第二个字符串,如果第二个字符串中所有的字符串对应的整数都能被前面得到的整数整除,那么第一个字符串包含第二个字符串。但是这种方法有一个致命的缺点,整数容易溢出,可以用支持大整数的语言来写,比如Python、Ruby。

def StringContain(L1, L2):
	primes = [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]
	
	m = 1;
	for ch in L1:
		m = m * primes[ord(ch) - ord('A')]

	for ch in L2:
		if m % primes[ord(ch) - ord('A')] != 0:
			return False;
	return True;