LC-567 Permutation in String

给两个字符串s1和s2，如果s2中包含s1的某个全排列，则返回true，否则返回false。

最直观的解法就是：

枚举s1的所有全排列。递归算法的时间复杂度为递归次数*单次递归的复杂度，递归树上每个非叶结点都是一次递归，树上共有\(O(n!)\)级别数目的非叶结点，因此递归调用次数为\(O(n!)\)。单次递归的复杂度为\(O(n)\)。因此这一步的时间复杂度为\(O(n\times n!)\)。递归调用的深度为\(O(n)\)，即空间复杂度\(O(n)\)。
对于每个全排列，check其是否为s2的子串。如果用KMP算法，时间复杂度为\(O((n_1+n_2)\times n_1!)\)，空间复杂度为\(O(n_1)\)。

综上，总的时间复杂度为\(O((2n_1+n_2)\times n_1!)\)，总的空间复杂度为\(O(n_1)\)。

Approach 1

我拿到此题的第一感觉是哈希表，首先统计s1中每种字符的频率，如果s2中存在一个长度为\(n_1\)的连续区间窗口，完全符合s1的字符频率表，则返回true。

如果当前窗口不符合要求，向右滑动，更新移除和加入窗口的字符频率，继续与s1的字符频率比对，直到s2结尾。

class Solution:
    def checkInclusion(self, s1: str, s2: str) -> bool:
        len1, len2 = len(s1), len(s2)
        m1 = collections.Counter(s1)
        m2 = collections.Counter(s2[:len1])
        if m1 == m2:
            return True
        for i in range(len1, len2):
            m2[s2[i]] += 1
            m2[s2[i - len1]] -= 1
            if m1 == m2:
                return True
        return False

比对2个哈希表的时间复杂度取决于不同字符的数目，这里为26，因此总的时间复杂度为\(O(26\times (n_2-n_1))\)，空间复杂度为\(O(1)\)。

Approach 2

方法一用到了2个哈希表，m1固定不变，m2随窗口的滑动而变化，并与m1对比每个字符的频率是否相等。因此可以转换思路，将对比每个字符的频率是否相等转换为：s1中每个字符的频率与s2窗口中每个字符频率的差值，只需要1个哈希表来记录s1与s2的字符频率差值即可。

先统计s1的字符频率表m，对于遍历到的s2的每个字符s2[r]：m[s2[r]]--

若m[s2[r]]<0，表明当前字符在s1中未曾出现，或者当前在s2窗口中的出现次数已经超过了在s1中的出现次数，说明窗口[l,r]中包含的字符太多，超出了s1的要求，此时我们移动窗口的左边界l++并更新m。如果移动后[l,r]中包含的字符仍然过多，继续l++并更新m，直到m[s2[r]]=0。
若m[s2[r]]=0，表明该字符在当前窗口内的频率与s1相同，且[l,r]内的字符频率都与s1相同，即m[s2[l...r]]=0，如果此时窗口大小正好等于\(n_1\)，返回true。
若m[s2[r]]>0，表明[l,r]内的字符不足以covers1，移动窗口的右边界r++。

class Solution:
    def checkInclusion(self, s1: str, s2: str) -> bool:
        l, r = 0, 0
        m = collections.Counter(s1)
        while r < len(s2):
            m[s2[r]] -= 1
            if m[s2[r]] < 0:
                while m[s2[r]] < 0:
                    m[s2[l]] += 1
                    l += 1
            elif m[s2[r]] == 0:
                if r - l + 1 == len(s1):
                    return True
            r += 1
        return False

Reference

字符串中的全排列