【算法】字符串的排列

难度：中等

给你两个字符串 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