做企业网站要用什么软件,个人网站 备案备注,钟楼做网站,外包岗位难度#xff1a;中等
给你两个字符串 s1 和 s2 #xff0c;写一个函数来判断 s2 是否包含 s1 的排列。如果是#xff0c;返回 true #xff1b;否则#xff0c;返回 false 。
换句话说#xff0c;s1 的排列之一是 s2 的 子串 。
示例 1#xff1a;
输入#xff1a;…难度中等
给你两个字符串 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所有字符的一个排列作为子串。
计数映射首先我们需要统计字符串s1中每个字符出现的次数可以用一个对象或Map来实现。这将帮助我们后续比较时快速判断一个子串是否为s1的排列。滑动窗口在s2上建立一个大小与s1相等的窗口初始时覆盖s2的前|s1|个字符|s1|表示字符串s1的长度。然后逐步将窗口向右滑动一位每次滑动时
增加新进入窗口的字符的计数。减少离开窗口的字符的计数。检查当前窗口内的字符计数是否与s1的计数映射完全匹配如果匹配则找到了一个排列子串返回true。
遍历结束未找到如果遍历完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
