怎么弄一个自己的网站,物联网设备,交易平台网站制作,jsp旅游网站开发系统LCR 014. 字符串的排列
给定两个字符串 s1 和 s2#xff0c;写一个函数来判断 s2 是否包含 s1 的某个变位词。
换句话说#xff0c;第一个字符串的排列之一是第二个字符串的 子串 。
示例 1#xff1a;
输入: s1 ab s2 eidbaooo
输出: True
解…LCR 014. 字符串的排列
给定两个字符串 s1 和 s2写一个函数来判断 s2 是否包含 s1 的某个变位词。
换句话说第一个字符串的排列之一是第二个字符串的 子串 。
示例 1
输入: s1 ab s2 eidbaooo
输出: True
解释: s2 包含 s1 的排列之一 (ba).示例 2
输入: s1 ab s2 eidboaoo
输出: False提示
1 s1.length, s2.length 104s1 和 s2 仅包含小写字母
法1滑动窗口
分析
建立一个hash表键是26个字母对应值是各自出现的次数为方便键0就代表a1代表b这样。
看例子s1 ab s2 eidbaooo 表格中没写的都是填充0。接着遍历后面的s2 i2,遍历s2中的d, counts[s2.charCodeAt(i) - ‘a’.charCodeAt(0)]–counts[d-a]–counts[3]– counts[s2.charCodeAt(i - s1.length) - ‘a’.charCodeAt(0)]counts[e-a]counts[4]
i3,遍历s2中的b counts[s2.charCodeAt(i) - ‘a’.charCodeAt(0)]–counts[b-a]–counts[1]– counts[s2.charCodeAt(i - s1.length) - ‘a’.charCodeAt(0)]counts[i-a]counts[8]
i4,遍历s2中的a counts[s2.charCodeAt(i) - ‘a’.charCodeAt(0)]–counts[a-a]–counts[0]– counts[s2.charCodeAt(i - s1.length) - ‘a’.charCodeAt(0)]counts[d-a]counts[3]
到这counts全都为0就返回true var checkInclusion function(s1, s2) {if (s2.length s1.length) return false;let counts new Array(26).fill(0);// 初始填充 counts 数组for (let i 0; i s1.length; i) {counts[s1.charCodeAt(i) - a.charCodeAt(0)]; // s1 计数 counts[s2.charCodeAt(i) - a.charCodeAt(0)]--; // s2 计数 --}// 检查是否已匹配if (areAllZero(counts)) {return true;}// 滑动窗口// 滑动窗口的大小始终为 s1.length。for (let i s1.length; i s2.length; i) {counts[s2.charCodeAt(i) - a.charCodeAt(0)]--;counts[s2.charCodeAt(i - s1.length) - a.charCodeAt(0)];if (areAllZero(counts)) {return true;}}
};/*** 辅助函数检查 counts 数组是否全部为零* param {number[]} counts* return {boolean}*/
function areAllZero(counts) {for (let count of counts) {if (count ! 0) {return false;}}return true;
}
