题目描述
给定两个分别由字母组成的字符串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。
使用hash的思想，如果字符在hash table中，则存在这个字符，否则就返回False
// 时间复杂度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中的字典类型
# -*- coding: utf-8 -*-
"""
Created on Mon Jun 5 21:45:05 2017
@author: Sean Chang
"""
def stringinclude(str1,str2):
dic1 = {}
for i in str1:
if (dic1.get(i)==None): #字典中没有这个字符，加入这个字符为key并设置value为1
dic1[i]=1
else:
dic1[i]=dic1[i]+1
for j in str2:
if dic1.get(j)==None:
return False
return True
def main():
str1='ABCD'
str2='BCE'
print(stringinclude(str1,str2))
main()
