438. Find All Anagrams in a String

Leetcode link

题目简介

/**
 * @param {string} s
 * @param {string} p
 * @return {number[]}
 */

题目给我们两个字符串 s 与 p，要求我们在 s 中找到所有由 p 字符串字符构成的子字符串并返回子字符串的开始坐标

解题思路

这题其实算是 76 题的简化版本，76 题的字符串是不连续的，而这一题只需要寻找连续的子字符串即可

方法还是一样，我们用一个 map 来保存 p 字符串中字符的个数，然后用一个 remainingCount 保存 p 字符串的长度，这样可以减少遍历 map 的复杂度

接下来我们只需要在右指针遍历新元素与左指针离开旧元素的时候维护好 remainingCount 与 map 即可

在 remainingCount 为 0 的时候我们把左指针 left 放进答案中就好

Javascript

/**
 * @param {string} s
 * @param {string} p
 * @return {number[]}
 */
var findAnagrams = function (s, p) {
    const map = new Map()
    let remainingCount = p.length
    for (const char of p) {
        map.set(char, (map.get(char) || 0) + 1)
    }
    const res = []

    let left = 0
    for (let right = 0; right < s.length; right++) {
        const char = s[right]
        if (map.has(char)) {
            if (map.get(char) > 0) {
                remainingCount--
            }
            map.set(char, map.get(char) - 1)
        }

        if (remainingCount === 0) {
            res.push(left)
        }

        if (right - left + 1 === p.length) {
            const leftChar = s[left]
            if (map.has(leftChar)) {
                map.set(leftChar, map.get(leftChar) + 1)
                if (map.get(leftChar) > 0) {
                    remainingCount++
                }
            }
            left++
        }
    }

    return res
};

解题思路

当然，作为 medium，这题自然还会有别的思路

如果我们仔细观察题目我们会发现 s 与 p 都只包含小写英文单字，所以我们只需要维护两个长度为 64 的字符串即可对比当前 s 的子字符串是否与 p 字符串有相同字符构成

Javascript

/**
 * @param {string} s
 * @param {string} p
 * @return {number[]}
 */
var findAnagrams = function (s, p) {
    const pCount = new Array(64).fill(0)
    const windowCount = new Array(64).fill(0)
    const res = []

    for (const char of p) {
        pCount[getIndex(char)]++
    }

    let left = 0
    let right = 0
    while (right < s.length) {
        windowCount[getIndex(s[right])]++

        if (right - left + 1 > p.length) {
            windowCount[getIndex(s[left])]--
            left++
        }

        if (isEqual(pCount, windowCount)) {
            res.push(left)
        }
        right++
    }

    return res
};

const getIndex = char => char.charCodeAt(0) - 97;
const isEqual = (count1, count2) => {
    for (let i = 0; i < count1.length; i++) {
        if (count1[i] !== count2[i]) {
            return false
        }
    }
    return true
}