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

题目描述

给定一个字符串 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" 的异位词。

提示：

• 1 <= s.length, p.length <= 3 * 104
• s 和 p 仅包含小写字母

出处：LeetCode

解法一：滑动窗口

思路

我们可以使用滑动窗口来解决这个问题。首先，我们需要统计字符串 p 中每个字符的出现次数，然后使用两个指针 left 和 right 来维护一个长度为 p.length 的窗口。我们可以使用一个哈希表 window 来记录窗口中每个字符的出现次数，以及一个哈希表 need 来记录字符串 p 中每个字符的出现次数。

在每一步中，我们将 right 指针向右移动一格，如果 window 中的字符数量等于 need 中的字符数量，我们就可以判断窗口中的字符串是 p 的字母异位词。接着，我们将 left 指针向右移动一格，缩小窗口，直到窗口中的字符串不再是 p 的字母异位词。

代码

function findAnagrams(s: string, p: string): number[] {
  const need = new Map<string, number>();
  const window = new Map<string, number>();
  const res: number[] = [];

  for (const c of p) {
    need.set(c, (need.get(c) || 0) + 1);
  }

  let left = 0;
  let right = 0;
  let valid = 0;

  while (right < s.length) {
    const c = s[right];
    right++;

    if (need.has(c)) {
      window.set(c, (window.get(c) || 0) + 1);
      if (window.get(c) === need.get(c)) {
        valid++;
      }
    }

    while (right - left >= p.length) {
      if (valid === need.size) {
        res.push(left);
      }

      const d = s[left];
      left++;

      if (need.has(d)) {
        if (window.get(d) === need.get(d)) {
          valid--;
        }
        window.set(d, window.get(d)! - 1);
      }
    }
  }

  return res;
}

我们也可以使用数组来代替哈希表，因为字符串中只包含小写字母，优化后代码如下：

function findAnagrams(s: string, p: string): number[] {
  const need = new Array(26).fill(0);
  const window = new Array(26).fill(0);
  const res: number[] = [];

  for (const c of p) {
    need[c.charCodeAt(0) - 'a'.charCodeAt(0)]++;
  }

  let left = 0;
  let right = 0;

  while (right < s.length) {
    const c = s[right];
    window[c.charCodeAt(0) - 'a'.charCodeAt(0)]++;
    right++;

    while (right - left >= p.length) {
      if (window.every((val, i) => val === need[i])) {
        res.push(left);
      }

      const d = s[left];
      window[d.charCodeAt(0) - 'a'.charCodeAt(0)]--;
      left++;
    }
  }

  return res;
}

复杂度分析

• 时间复杂度：$O(n)$，其中 $n$ 是字符串 s 的长度。我们只需要遍历一次字符串 s。
• 空间复杂度：$O(1)$。我们使用了常数大小的额外空间。