题目
假设这有一个各种字母组成的字符串，假设这还有另外一个字符串，而且这个字符串里的字母数相对少一些。从算法是讲，什么方法能最快的查出所有小字符串里的字母在大字符串里都有？
解法1
- 以长串的所有字符为key，value为True生成一字典
- 遍历短串，若字典中不存在短串的某一值返回 False
class Solution:
def IsStrContains(self, bigStrs, smallStrs):
strDict = {}
ans = True
for i, v in enumerate(bigStrs):
strDict[v] = True
for i, v in enumerate(smallStrs):
if not v in strDict:
ans = False
break
return ans
解法2
该方法局限性比较大，实用性也不高，但不失为一种好的思路
- 选取26个素数，第一个素数代表 A ，第二个代表 B
- 求出长串的素数之积
- 遍历短串，用积去除短串中每一个素数值，当有余数的时候返回 False
class Solution:
def IsStrContains(self,bigStrs,smallStrs):
# z之前的所有ASCII 素数
primerList = self.GetPrimer(ord('z'))
bigProd = 1
for v in bigStrs:
bigProd *= primerList[ord(v)-ord('A')]
for v in smallStrs:
if bigProd % primerList[ord(v)-ord('A')] != 0:
return False
return True
def GetPrimer(self, count):
if count <=0 :
return []
end = math.sqrt(count)
primerList =[2]
primerSize =1
i = 3
while primerSize != count:
if self.IsPrimder(i):
primerList.append(i)
primerSize +=1
i+=2
return primerList
def IsPrimder(self,num):
end = int(math.sqrt(num)) +1
for i in range(2,end):
if num % i ==0:
return False
return True
总结
在解决包含问题的时候可以考虑使用字典来达到空间换时间的效率