给定字符串A和短字符串B，最快的判断出B中的所有字符是否都在A中？假设所有字符都在ASCII表中。
例如：
A是“abcDeF”，B是“aaD”则返回true，
A是“abcDeF”，B是“aaBD”则返回false，
相当于字典问题，所有字符都在字典中出现则返回true，否则返回false。每一个字符都是一个符号，按题目要求只需标识是否存在，而不需标识出现次数。对测试字符串进行在字典字符串中的遍历，当然可以解决问题但是时间成本大。如果应用字典的的话会引入额外的数据结构，而且在空间上也并不是最优。于是有如下思路：本身目的就是为了标识，就是0、1问题，那就可以引入二进制每一位来标识。ASCII本身包含了128个字符，所以需要128位来标识每一个字符，在64位系统中python最大整数有64位其中包括符号位，则可用的有63位，则我们使用3个整数就可以标识128位字符，将三个整数排列起来忽略符号位共有189位，最多可标识189个字符。现在只需要找到每个ASCII字符对应位置即可。示意图如下：
python代码如下：
import sys
class StringContain:
listhash = []
maxlen = 63
def __init__(self):
self.maxlen = len(str(bin(sys.maxsize))) - 2
self.listhash=[0]*(128//self.maxlen+1)
def _getindex(self,c):
idx=ord(c)//self.maxlen
return idx,ord(c)-idx*self.maxlen
def test(self,string,test_string):
for i in string:
idx,tmpnum=self._getindex(i)
realnum = 2**tmpnum
self.listhash[idx] |= realnum
for j in testString:
idx, tmpnum = self._getindex(j)
realnum = 2**tmpnum
if (self.listhash[idx] & realnum) == 0:
return False
return True
测试代码如下：
A='abcDeF' B='aaD' sc=StringContain() print(sc.test(A,B)) A='abcDeF' B='aaBD' print(sc.test(A,B))
输出
True False
