字符串的排列

• https://leetcode.cn/problems/permutation-in-string/description/

描述

• 给你两个字符串 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 <= $10^4$
• s1 和 s2 仅包含小写字母

Typescript 版算法实现

1 ) 方案1：滑动窗口

function checkInclusion(s1: string, s2: string): boolean {const n: number = s1.length;const m: number = s2.length;// 如果 s1 的长度大于 s2，则不可能有排列包含在 s2 中if (n > m) {return false;}// 创建两个数组来存储 s1 和当前窗口中每个字符的频率const cnt1: number[] = new Array(26).fill(0);const cnt2: number[] = new Array(26).fill(0);// 统计 s1 和 s2 前 n 个字符的频率for (let i = 0; i < n; ++i) {cnt1[s1.charCodeAt(i) - 'a'.charCodeAt(0)]++;cnt2[s2.charCodeAt(i) - 'a'.charCodeAt(0)]++;}// 检查初始窗口是否匹配if (cnt1.toString() === cnt2.toString()) {return true;}// 滑动窗口遍历 s2 的其余部分for (let i = n; i < m; ++i) {// 更新当前窗口的频率计数cnt2[s2.charCodeAt(i) - 'a'.charCodeAt(0)]++;cnt2[s2.charCodeAt(i - n) - 'a'.charCodeAt(0)]--;// 检查当前窗口是否匹配if (cnt1.toString() === cnt2.toString()) {return true;}}return false;
}

2 ) 方案2：滑动窗口优化

function checkInclusion(s1: string, s2: string): boolean {const n: number = s1.length;const m: number = s2.length;// 如果 s1 的长度大于 s2，则不可能有排列包含在 s2 中if (n > m) {return false;}// 创建一个数组来存储字符频率差异const cnt: number[] = new Array(26).fill(0);// 统计 s1 和 s2 前 n 个字符的频率差异for (let i = 0; i < n; ++i) {--cnt[s1.charCodeAt(i) - 'a'.charCodeAt(0)];++cnt[s2.charCodeAt(i) - 'a'.charCodeAt(0)];}let diff: number = 0;for (const c of cnt) {if (c !== 0) {++diff;}}// 检查初始窗口是否匹配if (diff === 0) {return true;}// 滑动窗口遍历 s2 的其余部分for (let i = n; i < m; ++i) {const x: number = s2.charCodeAt(i) - 'a'.charCodeAt(0);const y: number = s2.charCodeAt(i - n) - 'a'.charCodeAt(0);if (x === y) {continue;}// 更新字符频率差异并调整 diffif (cnt[x] === 0) {++diff;}++cnt[x];if (cnt[x] === 0) {--diff;}if (cnt[y] === 0) {++diff;}--cnt[y];if (cnt[y] === 0) {--diff;}// 检查当前窗口是否匹配if (diff === 0) {return true;}}return false;
}

3 ) 方案3：双指针

function checkInclusion(s1: string, s2: string): boolean {const n: number = s1.length;const m: number = s2.length;// 如果 s1 的长度大于 s2，则不可能有排列包含在 s2 中if (n > m) {return false;}// 创建一个数组来存储字符频率差异const cnt: number[] = new Array(26).fill(0);// 统计 s1 的每个字符的频率差异for (let i = 0; i < n; ++i) {--cnt[s1.charCodeAt(i) - 'a'.charCodeAt(0)];}let left: number = 0;// 使用滑动窗口遍历 s2for (let right = 0; right < m; ++right) {const x: number = s2.charCodeAt(right) - 'a'.charCodeAt(0);++cnt[x];// 如果当前字符频率超出，调整左边界while (cnt[x] > 0) {--cnt[s2.charCodeAt(left) - 'a'.charCodeAt(0)];++left;}// 检查当前窗口大小是否与 s1 长度相等if (right - left + 1 === n) {return true;}}return false;
}