滑动窗口
解题思路
初始化两个 hash 数组，用于记录 s1 和 s2 中的字符；
滑动窗口的大小等于 s1 的长度，每次向右滑动的时候判断两个 hash 数组是否内容相等，相等则说明存在 子串；
窗口滑动的过程中，要维护窗口内的元素个数；
复杂度
-
时间复杂度：
O(N) -
空间复杂度：
O(1)
代码实现
function checkInclusion(s1, s2) {
if (s1.length > s2.length) return false;
// 1. 初始化两个 hash 数组
const hash1 = new Array(26).fill(0);
const hash2 = new Array(26).fill(0);
const offset = 'a'.charCodeAt(0);
// 2. 初始化频率数组，保证了窗口的大小与 s1 的长度一致
for (let i = 0; i < s1.length; i++) {
hash1[s1.charCodeAt(i) - offset]++;
hash2[s2.charCodeAt(i) - offset]++;
}
// 3. 滑动窗口
for (let i = s1.length; i <= s2.length; i++) {
// 判断窗口
if (check(hash1, hash2)) {
return true;
}
// 窗口向右滑动，维护窗口内的元素个数
hash2[s2.charCodeAt(i - s1.length) - offset]--;
hash2[s2.charCodeAt(i) - offset]++;
}
return false;
};
const check = (arr1, arry2) => {
for (let i = 0; i < 26; i++) {
if (arr1[i] !== arry2[i]) {
return false;
}
}
return true;
};
打赏作者
您的打赏是我前进的动力
微信
支付宝
leetcode🧑💻 151. 颠倒字符串中的单词
上一篇
评论
