https://leetcode-cn.com/explore/interview/card/bytedance/242/string/1016/
给定两个字符串 s1 和 s2，写一个函数来判断 s2 是否包含 s1 的排列。
换句话说，第一个字符串的排列之一是第二个字符串的子串。
示例1:
输入: s1 = "ab" s2 = "eidbaooo"
输出: True
解释: s2 包含 s1 的排列之一 ("ba").
示例2:
输入: s1= "ab" s2 = "eidboaoo"
输出: False
注意：
输入的字符串只包含小写字母
两个字符串的长度都在 [1, 10,000] 之间
思路：
最直接的思路是
- 把全排列其实直接转换成字符出现的次数自动，这样在str2中其实只要判断连续的有包含出现次数相同的字典就行
- 在实现str2包含是否含有str1出现次数的字典时，从str2首字母往后遍历str1长度，如果不满足出现次数相同，则继续从str2下一个开始找，这样的复杂度是O（len_str1*len_str2），用python实现中有用例超时的。
最佳的思路是对上面的进行改进，在遍历str2的时候，从头往后只走一次，每次走的时候一格的时候，更新目前str2中，从i到i+len_str1中的字符出现次数字典，如果两者一致，则返回true，否则继续更细。这样复杂度其实是O（max(len_str1,len_str2)）。在代码实现中，发现最好是哈希字典的方式去把所有字符出现的次数算好，否则需要在遍历str2的时候，动态需要删除/添加str2出现次数字典，会比较麻烦一些。
class Solution(object):
def checkInclusion(self, s1, s2):
"""
:type s1: str
:type s2: str
:rtype: bool
"""
if not s2 or not s1:
return False
s1_len = len(s1)
s2_len = len(s2)
if s1_len > s2_len:
return False
dict_s1 = {}
dict_s2 = {}
low_alpha = 'abcdefghijklmnopqrstuvwxyz'
for each_alpha in low_alpha:
dict_s1[each_alpha] = 0
dict_s2[each_alpha] = 0
for i in range(0, s1_len):
dict_s1[s1[i]] += 1
dict_s2[s2[i]] += 1
if dict_s1 == dict_s2:
return True
for i in range(s1_len, s2_len):
dict_s2[s2[i - s1_len]] -= 1
dict_s2[s2[i]] += 1
if dict_s1 == dict_s2:
return True
return False
