【算法】字符串的排列

难度：中等

给你两个字符串 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 仅包含小写字母

解题思路：

滑动窗口是处理字符串子串问题时常用的技术，通过在字符串上移动一个固定大小的窗口来检查不同的子串。我们的目标是检查字符串s2中是否存在s1所有字符的一个排列作为子串。

1. 计数映射：首先，我们需要统计字符串s1中每个字符出现的次数，可以用一个对象或Map来实现。这将帮助我们后续比较时，快速判断一个子串是否为s1的排列。
2. 滑动窗口：在s2上建立一个大小与s1相等的窗口，初始时覆盖s2的前|s1|个字符（|s1|表示字符串s1的长度）。然后，逐步将窗口向右滑动一位，每次滑动时：

• 增加新进入窗口的字符的计数。
• 减少离开窗口的字符的计数。
• 检查当前窗口内的字符计数是否与s1的计数映射完全匹配，如果匹配，则找到了一个排列子串，返回true。

3. 遍历结束未找到：如果遍历完s2仍未找到匹配的子串，则返回false。

JavaScript实现：

/**
 * @param {string} s1
 * @param {string} s2
 * @return {boolean}
 */
var checkInclusion = function (s1, s2) {
    if (s1.length > s2.length) return false; // s1长度大于s2，不可能为子串
    // 计算s1中各字符的计数
    const countMap = new Map();
    for (const char of s1) {
        countMap.set(char, (countMap.get(char) || 0) + 1);
    }
    console.log(countMap)
    // 定义滑动窗口的大小
    const windowSize = s1.length;
    // 循环遍历的时候一定要记住减去
    for (let i = 0; i <= s2.length - windowSize; i++) {
        // 重置滑动窗口的计数映射，为什么要重置滑动窗口？是因为在下面的for j循环中对tempMap进行改动，所以在每次for i循环中都需要对tempMap进行重置
        const tempMap = new Map(countMap);
        console.log(tempMap)

        // 检查当前窗口内的字符
        for (let j = 0; j < windowSize; j++) {
            const char = s2[i + j];
            if (tempMap.has(char)) {
                tempMap.set(char, tempMap.get(char) - 1);
                // 如果计数为0，可以从映射中移除
                if (tempMap.get(char) === 0) tempMap.delete(char);
            } else { // 如果不是的话，一定要跳出循环，要不然执行会超时
                break; // 当前字符不在s1的映射中，直接跳出循环
            }
        }
        // 如果映射为空，说明当前窗口内的字符与s1的排列一致
        if (tempMap.size === 0) return true;
    }
    return false; // 遍历结束，未找到匹配的子串
};
console.log(checkInclusion("ab", "eidbaooo")); // 输出: true
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38