字符串的排列

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] 之间

思路：
最直接的思路是

1. 把全排列其实直接转换成字符出现的次数自动，这样在str2中其实只要判断连续的有包含出现次数相同的字典就行
2. 在实现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