LeetCode 438：找到字符串中的所有相同字母异序词

题目：LeetCode 438：Find All Anagrams in a String^[1]

要求：给定一个字符串 s 和 一个非空字符串 p，找到 s 中有关 p 的所有异序词的开始下标。

示例1：

输入：s= "cbaebabacd"，p= "abc"
输出：[0, 6]
解释：
下标 0 对应着 "cba"，它是 p 的异序词。
下标 6 对应着 "bac"，它是 p 的异序词。

示例2：

输入：s= "abab"，p= "ab"
输出：[0, 1, 2]

分析：

该题和上一篇 《LeetCode 76: 最小窗口子串(Minimum Window Substring)》 几乎一样，只是有个限定条件，找到的子串要和目标串长度一致。所以，在上题的代码基础上，稍作改动即可：

function findAnagrams(s, p) {

    // 存放符合条件的下标
    const ans = [];

    if (s.length < p.length) {
        // 源字符串比目标串短，不可能存在异序词，直接返回
        return ans;
    }

    // 构造目标串的频率表
    const table = [];
    for (const c of p) {
        table[c] = (table[c] || 0) + 1;
    }

    let begin = 0
      , end = 0
      , counter = Object.keys(table).length
      , wordSize = p.length;

    while (end < s.length) {
        const endchar = s[end];

        if (endchar in table) {
            table[endchar]--;

            if (table[endchar] === 0) {
                counter--;
            }
        }

        end++;

        while (counter === 0) {

            // 找到了异序词
            if (end - begin === wordSize) {
                ans.push(begin);
            }

            const beginchar = s[begin];

            if (beginchar in table) {
                table[beginchar]++;
                if (table[beginchar] > 0) {
                    counter++;
                }

            }
            // 窗口右移
            begin++;
        }

    }
    return ans;
}

参考资料