leetcode 567 字符串的排列
给你两个字符串 s1 和 s2 ，写一个函数来判断 s2 是否包含 s1 的排列。如果是，返回 true ；否则，返回 false 。
换句话说，s1 的排列之一是 s2 的 子串 。
示例1
输入：s1 = "ab" s2 = "eidbaooo"
输出：true
解释：s2 包含 s1 的排列之一 ("ba").
示例2
输入：s1= "ab" s2 = "eidboaoo"
输出：false
思路
通过一个数组，先计算出左字符串中每个字符出现的频率，然后再遍历有字符串，对比两者的出现频率，通过一个 count 计数器，来判断左字符串中的所有字符是否都在右字符串中全部出现过，判断依据就是 count === 0
代码
/**
* @param {string} s1
* @param {string} s2
* @return {boolean}
*/
function getCharCodeDistance(a, b) {
return a.charCodeAt() - b.charCodeAt();
}
function checkInclusion(s1, s2) {
const freq = new Array(256).fill(0);
if (s2.length === 0 || s2.length < s1.length) {
return false;
}
for (let i = 0; i < s1.length; i++) {
freq[getCharCodeDistance(s1[i], 'a')]++;
}
let left = 0;
let right = 0;
let count = s1.length;
while (right < s2.length) {
if (freq[getCharCodeDistance(s2[right], 'a')] >= 1) {
count--;
}
freq[getCharCodeDistance(s2[right], 'a')]--;
right++;
if (count === 0) {
return true;
}
if (right - left === s1.length) {
if (freq[getCharCodeDistance(s2[left], 'a')] >= 0) {
count++;
}
freq[getCharCodeDistance(s2[left], 'a')]++;
left++;
}
}
return false;
}
复杂度分析:
- 时间复杂度: O(N)
- 空间复杂度：O(1)