1.题目
给定两个字符串 s1 和 s2，写一个函数来判断 s2 是否包含 s1 的排列。
换句话说，第一个字符串的排列之一是第二个字符串的子串。
示例1：
输入: s1 = "ab" s2 = "eidbaooo"
输出: True
解释: s2 包含 s1 的排列之一 ("ba").
示例2：
输入: s1= "ab" s2 = "eidboaoo"
输出: False
注意：
输入的字符串只包含小写字母
两个字符串的长度都在 [1, 10,000] 之间
2.分析
- 思路1：暴力，首先想到将
s1构造成一个字典，然后以s1的长度为窗口，不断在s2上滑动构造字典，比较两个字典是否一致，如果一致就是True，可以这个暴力方法在构造字典方面速度太慢，妥妥的时间超时。 - 思路2：使用滑动窗口（上面的思路一致），不过这个写法省略了不断构造字典的问题，提高了速度。
- 思路3：目前市面上能看到最快最节约内存的方法，通过直接构造包含26个字母为key的字典，省去了在添加时候的判断，提高了效率。
3.解决
- 思路1：暴力解法，不断构造字典，看其中元素是否和
target字典一致，嘻嘻，直接超时。
class Solution:
def checkInclusion(self, s1: str, s2: str):
if not s1 or not s2 or len(s1) > len(s2):
return False
target_dict = {}
for i in s1:
if i not in target_dict:
target_dict[i] = 1
else:
target_dict[i] += 1
print(target_dict)
length_s1 = len(s1)
j = 0
while j + length_s1 <= len(s2):
tmp_s2 = s2[j:j + length_s1]
tmp_dict = {}
for i in tmp_s2:
if i in tmp_dict:
tmp_dict[i] = tmp_dict[i] + 1
else:
tmp_dict[i] = 1
if tmp_dict == target_dict:
return True
j += 1
return False
if __name__ == '__main__':
a = "ab"
b = "eidbaooo"
s = Solution()
s.checkInclusion(a, b)
- 思路2：使用滑动窗口（上面的思路一致），不过这个写法省略了不断构造字典的问题，提高了速度
class Solution:
def checkInclusion(self, s1: str, s2: str) -> bool:
if len(s1) > len(s2):
return False
s1_hash = {}
s2_hash = {}
for i in range(len(s1)):
if s1[i] not in s1_hash.keys():
s1_hash[s1[i]] = 1
else:
s1_hash[s1[i]] += 1
if s2[i] not in s2_hash.keys():
s2_hash[s2[i]] = 1
else:
s2_hash[s2[i]] += 1
if s2_hash == s1_hash:
return True
else:
left = 0
right = len(s1)
while right < len(s2):
s2_hash[s2[left]] -= 1
if s2_hash[s2[left]] == 0:
s2_hash.pop(s2[left])
left += 1
if s2[right] in s2_hash.keys():
s2_hash[s2[right]] += 1
else:
s2_hash[s2[right]] = 1
right += 1
if s2_hash == s1_hash:
return True
return False
- 思路3：leetcode目前最快最节约内存解法
class Solution:
def checkInclusion(self, s1, s2):
l1 = len(s1)
l2 = len(s2)
if s1 == s2:
return True
if l2 < l1:
return False
s = "abcdefghijklmnopqrstuvwxyz"
dict1 = {}
dict2 = {}
for i in range(len(s)):
dict1[s[i]] = 0
dict2[s[i]] = 0
for i in range(l1):
dict1[s1[i]] += 1
dict2[s2[i]] += 1
if dict1 == dict2:
return True
for i in range(l2 - l1):
dict2[s2[i]] -= 1
dict2[s2[i + l1]] += 1
if dict1 == dict2:
return True
return False
if __name__ == '__main__':
s = Solution()
s1 = "ab"
s2 = "eidbaooo"
print(s.checkInclusion(s1, s2))
