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

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

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

异位词 指由相同字母重排列形成的字符串（包括相同的字符串）。

示例 1：

输入：s = “cbaebabacd”, p = “abc”
输出：[0,6]

示例 2：

输入：s = “abab”, p = “ab”
输出：[0,1,2]

提示：

• 1 <= s.length, p.length <= $3 * 10^4$
• s 和 p 仅包含小写英文字母

解析

固定大小的滑动窗口，用字符频率数组比较。

/**
 * @param {string} s
 * @param {string} p
 * @return {number[]}
 */
var findAnagrams = function (s, p) {
  const result = [];
  if (s.length < p.length) return result;

  const pCount = new Array(26).fill(0);
  const sCount = new Array(26).fill(0);
  const base = "a".charCodeAt(0);

  for (const ch of p) pCount[ch.charCodeAt(0) - base]++;

  for (let i = 0; i < s.length; i++) {
    sCount[s.charCodeAt(i) - base]++;
    if (i >= p.length) {
      sCount[s.charCodeAt(i - p.length) - base]--;
    }
    if (i >= p.length - 1) {
      if (sCount.every((val, idx) => val === pCount[idx])) {
        result.push(i - p.length + 1);
      }
    }
  }
  return result;
};

固定窗口大小为 p.length，滑动时加入右端字符、移除左端字符，比较频率数组。时间复杂度 O(n * 26) = O(n)。