567. 字符串的排列 Medium

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

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

示例 1：
输入：s1 = "ab" s2 = "eidbaooo"
输出：true
解释：s2 包含 s1 的排列之一 ("ba").

示例 2：
输入：s1= "ab" s2 = "eidboaoo"
输出：false

解题思路

输入：两个字符串 s1 和 s2

输出：判断 s2 中是否存在 s1 的一个排列子串

本题属于固定长度滑动窗口类型问题。

我们可以使用一个长度为 s1 的滑动窗口在 s2 上移动，并在窗口内实时统计字符频率。同时，使用两个计数器（数组或哈希表）分别记录 s1 和当前窗口中每个字母出现的次数。每次窗口移动时，只需更新进入和移出的字符计数，然后比较两个计数器是否相等。若某一时刻窗口内字符频率与 s1 完全一致，则说明找到了一个有效排列，返回 True。如果遍历结束仍未找到，返回 False。

本题难点在于要想到用数组或者哈希对比窗口内字母出现次数的逻辑。

代码实现

python

class Solution:
    def checkInclusion(self, s1: str, s2: str) -> bool:
        len_s1, len_s2 = len(s1), len(s2)

        if len_s1 > len_s2:
            return False

        count1 = [0] * 26  # 统计 s1 中每个字符的出现次数
        count2 = [0] * 26  # 滑动窗口中 s2 的字符统计

        for i in range(len_s1):
            count1[ord(s1[i]) - ord('a')] += 1
            count2[ord(s2[i]) - ord('a')] += 1

        # 开始滑动窗口
        for i in range(len_s2 - len_s1):
            if count1 == count2:
                return True
            # 移除左边的字符，添加右边的字符
            count2[ord(s2[i]) - ord('a')] -= 1
            count2[ord(s2[i + len_s1]) - ord('a')] += 1

        # 别忘了最后一轮窗口的比较
        return count1 == count2

javascript

const checkInclusion = function(s1, s2) {
    const n1 = s1.length, n2 = s2.length;
    if (n1 > n2) return false; // 如果 s1 比 s2 长，不可能包含其排列

    const aCode = 'a'.charCodeAt(0); // 提前计算 'a' 的 ASCII 值，方便后续索引
    const count1 = Array(26).fill(0); // 统计 s1 中每个字母的出现次数
    const count2 = Array(26).fill(0); // 滑动窗口中 s2 的字母统计

    // 初始化窗口：统计前 n1 个字符
    for (let i = 0; i < n1; i++) {
        count1[s1.charCodeAt(i) - aCode]++;
        count2[s2.charCodeAt(i) - aCode]++;
    }

    let matches = 0; // 统计两个计数数组在每个字母位置是否一致的个数
    for (let i = 0; i < 26; i++) {
        if (count1[i] === count2[i]) matches++;
    }

    // 开始滑动窗口
    for (let i = 0; i < n2 - n1; i++) {
        if (matches === 26) return true; // 如果所有字母出现次数都相等，说明找到一个排列

        const left = s2.charCodeAt(i) - aCode;        // 将滑出窗口的字符
        const right = s2.charCodeAt(i + n1) - aCode;   // 将滑入窗口的字符

        // 移除左边字符前，判断该字符是否与 s1 中相等，减少匹配数
        if (count2[left] === count1[left]) matches--;
        count2[left]--; // 移除左边字符
        if (count2[left] === count1[left]) matches++; // 更新匹配状态

        // 添加右边字符前，判断是否与 s1 中相等，减少匹配数
        if (count2[right] === count1[right]) matches--;
        count2[right]++; // 添加右边字符
        if (count2[right] === count1[right]) matches++; // 更新匹配状态
    }

    // 最后一次窗口检查
    return matches === 26;
};

复杂度分析

时间复杂度：O(n)

空间复杂度：O(1)

链接

567 国际版

567 中文版