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

LeetCode 原题链接

题目描述

给定两个字符串 s 和 p，找到 s 中所有与 p 互为字母异位词的子串，返回这些子串的起始下标。

字母异位词使用的字符及每个字符的出现次数相同，只是排列顺序可能不同。

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

解释：
s[0..2] = "cba"，是 "abc" 的字母异位词
s[6..8] = "bac"，是 "abc" 的字母异位词

题型判断

假设 p 的长度为 m。它的字母异位词长度一定也是 m，所以只需要检查 s 中每个长度为 m 的子串。

相邻的两个候选子串高度重叠：

s = "cbaebabacd"，窗口长度 = 3

[c b a] e b a b a c d
 c [b a e] b a b a c d
     ↑ 删除 c，加入 e

窗口向右移动一格时，只有两个字符发生变化：

  • 左边一个字符离开窗口。
  • 右边一个字符进入窗口。

因此不必重新统计整个子串，可以用定长滑动窗口维护字符频次。

核心思路

题目只包含小写英文字母，可以使用长度为 26 的数组记录每个字符出现的次数：

  • pCount[i]：字符在 p 中出现的次数。
  • windowCount[i]：字符在当前窗口中出现的次数。

当两个数组的 26 个位置全部相等时，当前窗口就是 p 的字母异位词。

为了避免每移动一次窗口都重新比较 26 个位置，再维护一个变量 matches：

matches = 频次相等的字符种类数量

当 matches === 26 时，说明所有字符的频次都相同。

如何维护 matches？

窗口滑动时只会改变离开字符和进入字符的频次。修改某个字符的频次前后，分别检查它是否与目标频次相等：

const updateWindow = (index, change) => {
  // 修改前相等，马上要破坏这个旧状态
  if (windowCount[index] === pCount[index]) {
    matches--;
  }

  windowCount[index] += change;

  // 修改后相等，记录这个新状态
  if (windowCount[index] === pCount[index]) {
    matches++;
  }
};
  • 字符进入窗口时，change = 1。
  • 字符离开窗口时，change = -1。

这样每次滑动只需更新两个字符，不需要重新扫描窗口或比较整个数组。

示例推演

以 s = "cbaebabacd"、p = "abc" 为例，窗口长度为 3：

窗口范围窗口内容离开进入是否为异位词
[0, 2]cba——是，记录 0
[1, 3]baece否
[2, 4]aebbb否
[3, 5]ebaaa否
[4, 6]babeb否
[5, 7]ababa否
[6, 8]bacac是，记录 6
[7, 9]acdbd否

注意 [1, 3] → [2, 4] 时，离开和进入的字符都是 b。依次执行一次减一和一次加一后，频次会恢复原值，matches 仍然正确。

推荐：更容易理解的实现

第一次做这道题，不必急着维护 matches。直接比较两个长度为 26 的频次数组，代码更直观：

var findAnagrams = function (s, p) {
  const windowLength = p.length;

  // s 比 p 短，不可能找到长度相同的异位词
  if (s.length < windowLength) {
    return [];
  }

  const result = [];
  const pCount = new Array(26).fill(0);
  const windowCount = new Array(26).fill(0);
  const baseCode = 'a'.charCodeAt(0);

  // 统计 p 和第一个窗口的字符频次
  for (let i = 0; i < windowLength; i++) {
    pCount[p.charCodeAt(i) - baseCode]++;
    windowCount[s.charCodeAt(i) - baseCode]++;
  }

  // 判断两个频次数组是否完全相同
  const countsAreEqual = () => {
    for (let i = 0; i < 26; i++) {
      if (pCount[i] !== windowCount[i]) {
        return false;
      }
    }
    return true;
  };

  // 检查第一个窗口
  if (countsAreEqual()) {
    result.push(0);
  }

  // 从第二个窗口开始，不断向右滑动
  for (let right = windowLength; right < s.length; right++) {
    // right - windowLength 是即将离开窗口的字符下标
    const outgoing = s.charCodeAt(right - windowLength) - baseCode;
    const incoming = s.charCodeAt(right) - baseCode;

    windowCount[outgoing]--; // 左侧字符离开
    windowCount[incoming]++; // 右侧字符进入

    if (countsAreEqual()) {
      // 当前窗口范围是 [right - windowLength + 1, right]
      result.push(right - windowLength + 1);
    }
  }

  return result;
};

这份代码只需要记住三件事：

  1. 先统计 p 和第一个窗口的字符次数。
  2. 窗口右移时，删除左边字符、加入右边字符。
  3. 两个频次数组相同，就记录窗口起点。

字符集固定为 26 个小写字母，所以每个窗口最多比较 26 次。时间复杂度为 O(26 × |s| + |p|)，去掉常数后仍是 O(|s| + |p|)；额外空间复杂度为 O(1)。

进阶：使用 matches 减少比较次数

理解基础实现后，可以用前文介绍的 matches 避免每个窗口都检查 26 个位置。这个版本常数更小，但状态维护更复杂，面试中优先写自己最有把握的版本即可。

var findAnagrams = function (s, p) {
  const windowLength = p.length;

  // s 比 p 短，不可能包含长度与 p 相同的子串
  if (s.length < windowLength) {
    return [];
  }

  const result = [];
  const pCount = new Array(26).fill(0);
  const windowCount = new Array(26).fill(0);
  const baseCode = 'a'.charCodeAt(0);

  // 同时统计 p 和 s 中第一个窗口的字符频次
  for (let i = 0; i < windowLength; i++) {
    pCount[p.charCodeAt(i) - baseCode]++;
    windowCount[s.charCodeAt(i) - baseCode]++;
  }

  // 统计有多少种字符在两个频次数组中的计数相等
  let matches = 0;
  for (let i = 0; i < 26; i++) {
    if (pCount[i] === windowCount[i]) {
      matches++;
    }
  }

  // 修改窗口内某个字符的频次，并同步维护 matches
  const updateWindow = (index, change) => {
    if (windowCount[index] === pCount[index]) {
      matches--;
    }

    windowCount[index] += change;

    if (windowCount[index] === pCount[index]) {
      matches++;
    }
  };

  // 检查第一个窗口
  if (matches === 26) {
    result.push(0);
  }

  // right 是新进入窗口的字符下标
  for (let right = windowLength; right < s.length; right++) {
    // 新窗口的左边界，也是上一个窗口中离开字符的下标
    const left = right - windowLength;
    const outgoingIndex = s.charCodeAt(left) - baseCode;
    const incomingIndex = s.charCodeAt(right) - baseCode;

    updateWindow(outgoingIndex, -1);
    updateWindow(incomingIndex, 1);

    if (matches === 26) {
      // 滑动完成后，新窗口的起始下标是 left + 1
      result.push(left + 1);
    }
  }

  return result;
};

正确性说明

算法始终维护以下不变量：

  1. windowCount 准确记录当前长度为 p.length 的窗口内各字符的频次。
  2. matches 准确记录 windowCount 与 pCount 中频次相等的位置数量。

初始化时直接统计第一个窗口，所以不变量成立。窗口右移时，只删除离开的字符并加入新字符，updateWindow 又分别维护了修改前后的相等状态，因此不变量继续成立。

两个字符串互为字母异位词，当且仅当 26 种字符的频次全部相同，也就是 matches === 26。因此算法记录的下标恰好是所有符合条件的窗口起点。

复杂度分析

  • 时间复杂度：O(|s| + |p|)。初始化需要遍历 p 和第一个窗口，之后每个字符至多进入、离开窗口各一次。
  • 空间复杂度：O(1)。两个频次数组的长度固定为 26，与输入规模无关。
  • 返回结果所占的空间不计入额外空间。

为什么不对每个子串排序？

可以截取每个长度为 m 的子串，排序后与排好序的 p 比较，但一共有约 |s| 个窗口，每个窗口排序需要 O(m log m) 时间，整体为 O(|s| × m log m)，还会频繁创建子串和数组。

滑动窗口利用了相邻窗口只变化两个字符的特点，避免了重复统计和排序。

易错点

  • 窗口长度必须固定为 p.length；异位词不可能改变字符串长度。
  • 忘记单独检查第一个窗口，导致遗漏下标 0。
  • 滑动时只加入新字符，忘记删除离开的字符。
  • 新窗口的起始下标是 right - p.length + 1，在本文变量中就是 left + 1。
  • 只比较出现过的字符种类，不比较出现次数，例如会把 aab 和 abb 错判为异位词。
  • 使用 sort() 时忘记它默认按字符串顺序排序或会原地修改数组。

面试时怎么说

异位词长度一定等于 p 的长度，因此使用定长滑动窗口。分别统计 p 和当前窗口的 26 个字符频次。窗口每次右移时，删除左边字符并加入右边字符；如果两个频次数组相同，就记录窗口左端点。因为字符集大小固定为 26，时间复杂度是 O(|s| + |p|)，额外空间复杂度是 O(1)。

自测

  1. 为什么窗口长度必须等于 p.length？
  2. 窗口右移一格时，哪些字符的频次会发生变化？
  3. 为什么修改频次前后都要更新一次 matches？
  4. 当离开和进入窗口的是同一个字符时，算法是否仍然正确？