JS_LeetCode09：找到字符串中所有字母异位词

image-20250516000621834

9.找到字符串中所有字母异位词

给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。

滑动窗口

这道题依然是利用滑动窗口的思想。不过这一次的滑动窗口的宽度是固定的，为目标子串的长度。也就是沿着字符串，滑动固定长度的窗口，去比较当前窗口内的字符串是否是子串的异位词。

？怎么判断是不是异位词呢

这里我首先想到的是将窗口内的子串进行排序，与排序后的目标子串做比较，如果两者相同，就满足条件。

但是排序的时间复杂度较高，因此提交题目会超时。

这时候需要换个角度，如果不依赖排序，那么异位词还有什么特点呢？

是的，那就是它们不同字符出现的次数是相同的。

数组计数

将目标子串的字符和出现次数记录下来，可以用Map，也可以用数组，数组会更简单些。

首先初始化一个长度为26的全0数组，索引代表字符在字母表上的顺序。

1
Array(26).fill(0)

如何更新字符的次数呢？这里需要利用Unicode编码！会返回字符对应的整数值，而连续的小写字母对应的整数值也是连续的。可以从’a’开始计算，后面的字符与’a’的Unicode编码（97）相差的大小对应着存放索引上的距离。

1
str.charCodeAt(index)

将窗口内的字符统计数组与目标字串的字符统计数组做对比，如果相同，则满足条件（我是逐元素对比）

解答

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
/**
 * @param {string} s
 * @param {string} p
 * @return {number[]}
 */
var findAnagrams = function(s, p) {
    let countP = Array(26).fill(0)
    const length = p.length
    const aCodeIndex = 'a'.charCodeAt(0)
    for (const char of p){
        let index = char.charCodeAt(0) - aCodeIndex
        countP[index] += 1
    }
    let res = []
    for (let i=0;i<=s.length-length;i++){
        let countS = Array(26).fill(0)
        let left = i;
        let right = i+length-1
        let matched = true
        for (const char of s.slice(left,right+1)){
            let index = char.charCodeAt(0) - aCodeIndex
            countS[index] += 1
        }
        for (let j=0;j<26;j++){
            if (countP[j]!=countS[j]){
                matched = false
                break
            }
        }
        if (matched){
            res.push(left)
        }
    }
    return res
};