字符串的排列（LeetCode 567）

1.问题描述

给你两个字符串 s1 和 s2 ，写一个函数来判断 s2 是否包含 s1 的排列。如果是，返回 true ；否则，返回 false 。

换句话说，s1 的排列之一是 s2 的 子串 。

示例 1：

输入：s1 = "ab" s2 = "eidbaooo"
输出：true
解释：s2 包含 s1 的排列之一 "ba"

示例 2：

输入：s1= "ab" s2 = "eidboaoo"
输出：false

提示：

• 1 <= s1.length, s2.length <= 104
• s1 和 s2 仅包含小写字母

2.难度等级

Medium。

3.热门指数

★★★★☆

出题公司：腾讯、富途。

4.解题思路

4.1 滑动窗口

由于排列不会改变字符串中每个字符的个数，所以只有当两个字符串每个字符的个数均相等时，一个字符串才是另一个字符串的排列。

根据这一性质，统计 s1 的字符个数，然后使用滑动串口遍历 s2，统计串口内字符个数是否需 s1 的相等。

如果相等，那么 s2 包含 s1 的排列之一，返回 true。

如果遍历完 s2 仍未找到 s1 的排列之一，返回 false。

注意，因为字符仅包含 26 个小写字母，所以统计字符个数可以使用一个长度为 26 的数组，数组下标与 26 个小写字母一一对应。

时间复杂度： O(m+n)，其中 m 为 s1 长度，n 为 s2 长度。

空间复杂度： O(Σ)，其中 Σ 是字符集字符数，这道题中的字符集是小写字母，所以 Σ 为 26。

下面以 Go 为例给出实现。

func checkInclusion(s1, s2 string) bool {
    n, m := len(s1), len(s2)
    if n > m {
        return false
    }
    var cnt1, cnt2 [26]int
    for i, ch := range s1 {
        cnt1[ch-'a']++
        cnt2[s2[i]-'a']++
    }
    if cnt1 == cnt2 {
        return true
    }
    for i := n; i < m; i++ {
        cnt2[s2[i]-'a']++
        cnt2[s2[i-n]-'a']--
        if cnt1 == cnt2 {
            return true
        }
    }
    return false
}

4.2 双指针

参考文献

567.字符串的排列 - LeetCode