leetCode 567. 字符串的排列

给你两个字符串 s1 和 s2 ，写一个函数来判断 s2 是否包含 s1 的排列。如果是，返回 true ；否则，返回 false 。

换句话说，s1 的排列之一是 s2 的 子串 。

示例 1：

输入：s1 = “ab” s2 = “eidbaooo”
输出：true
解释：s2 包含 s1 的排列之一 (“ba”).

解题思路

由示例可知，s1是s2 的子串的排列之一，也就是说在s2的s1长度的区间内，只要包含有相同元素，并且相同元素的数量相同，只用考虑元素数量，不用考虑元素的排列顺序，即为true，利用双指针，在s1的长度区间内去寻找

1. 创建一个map，记录s1当前出现的元素和次数，因为全部都是小写字母，所以所有的减去'a'.charCodeAt()就是0 - 26，fill 初始值填充为0
2. 出现一次就在相对应的位置 -1
3. 循环s2，记录s2出现的字符，并且在相对应的位置++，因为出现过的 都是 负数，所以继续循环，吧没有在s1中出现过的–，并且更新左指针
4. 一直循环，如果出现了s1中包含的子串，停止更新左指针
5. 并且判断左指针和右指针中的间隔，是否是s1的长度，如果是 返回true
6. 如果循环完毕，左右指针的间隔没有等于 s1 的长度 说明，没有相等的子串，返回false

/**
 * @param {string} s1
 * @param {string} s2
 * @return {boolean}
 */
 var checkInclusion = function(s1, s2) {
    let left = 0;
    let s1len = s1.length,
    s2len = s2.length

    const cnt = new Array(26).fill(0);

    const povit = 'a'.charCodeAt();

    for (let i = 0; i < s1len; i++) {
        --cnt[s1[i].charCodeAt() - povit];
    }

    for (let right = 0; right < s2len; right++) {
        const x = s2[right].charCodeAt() - povit;
        ++cnt[x];


        while(cnt[x] > 0) {
            const y = s2[left].charCodeAt() - povit;
            --cnt[y];
            left++;
        }
        if (right - left + 1 === s1.length) {
            return true;
        }
    }
    return false

};


let a = checkInclusion('ab','eidbaooo')
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39