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

题目描述

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

示例 1:
输入: s = “cbaebabacd”, p = “abc”
输出: [0,6]
解释:
起始索引等于 0 的子串是 “cba”, 它是 “abc” 的异位词。 起始索引等于 6 的子串是 “bac”, 它是 “abc” 的异位词。

示例 2:
输入: s = “abab”, p = “ab”
输出: [0,1,2]
解释:
起始索引等于 0 的子串是 “ab”, 它是 “ab” 的异位词。 起始索引等于 1 的子串是 “ba”, 它是 “ab” 的异位词。 起始索引等于 2 的子串是 “ab”, 它是 “ab” 的异位词。

思路&js代码

1、滑动窗口

function findAnagrams(s, p) {
    if (s.length < p.length) return []
 
    const map = new Map()
 
    for (let i = 0; i < p.length; i++) {
        const char = p[i]
        map.set(char, (map.get(char) || 0) + 1)
    }
 
    for (let i = 0; i < p.length; i++) {
        const char = s[i]
        if (map.has(char)) {
            map.set(char, map.get(char) - 1)
        }
    }
 
    const result = []
    for (let left = 0, right = p.length; right <= s.length; left++, right++) {
        if (Array.from(map.values()).every(item => item === 0)) result.push(left)
 
        if (map.has(s[left])) map.set(s[left], map.get(s[left]) + 1)
        if (map.has(s[right])) map.set(s[right], map.get(s[right]) - 1)
    }
 
    return result
};