手帐 Blog

主题

复盘 · LC 438 找到字符串中所有字母异位词 ​

题目 ​

题意 ​

给字符串 s 与模式串 p，找出 s 中所有子串，使得该子串是 p 的字母异位词（字符种类与个数相同，顺序可变），返回这些子串的起始下标（任意顺序）。

  • 窗口长度固定为 p.length。
  • s、p 只含小写字母；s 最长约 3×10⁴ 量级时，每窗再排序很容易 TLE。

边界：p 比 s 长 → []；p 有重复字母；多个重叠命中（如 s="abab", p="ab" → [0,1,2]）。

涉及算法 ​

标签一句话
定长滑动窗口窗长 = p.length；右移一格只改进/出一个字符
计数 / 哈希比较两个长度 26 的频次数组是否相等
排序指纹异位词 ⟺ 排序后相等；每窗全排太慢

教程对照：07 · 滑动窗口；异位词直觉可回扣 09 · 哈希表进阶（49 分组同源）。

评价我的解法 ​

思路：对 p 排序得指纹；每个定长子串也排序，相等则记下起点。正确性方向对（异位词判定），但规模与实现细节都撑不住——注释写明 28/65 超时。

我的代码（摘自 438-找到字符串中所有字母异位词/index.js，不含测例）：

javascript
function sortStr(s) {
  return s
    .split("")
    .sort((a, b) => {
      console.log(a, b, a > b);
      return a > b === true ? 1 : -1;
    })
    .join("");
}

var findAnagrams = function (s, p) {
  const subLen = p.length;
  const sortP = sortStr(p);
  let i = 0,
    j = subLen - 1;
  const resArr = [];
  for (; j < s.length; i++, j = i + subLen - 1) {
    const subStr = s.substring(i, j + 1);
    const sortSubStr = sortStr(subStr);
    if (sortSubStr === sortP) {
      resArr.push(i);
    }
  }
  return resArr;
};

对在哪：

  1. 定长窗枚举（i 起点、j = i + len - 1）骨架清楚。
  2. 异位词 = 排序后相同，和 49 字母异位词分组同一判据，知识点没跑偏。

错/糙在哪：

  1. 复杂度：约 (n-m+1) 次、每次 O(m log m) 排序 → 接近 O(n m log m)，大数据必 TLE。定长异位词应 O(n) 滑窗计数。
  2. console.log 写在 sort 比较器里：比较次数是排序的主成本量级，日志再乘一层，超时雪上加霜；提交/本地大测都要先拔掉。
  3. 比较器不规范：a === b 时仍返回 -1（应返回 0）；应用 a.localeCompare(b) 或 a.charCodeAt(0) - b.charCodeAt(0)。即便碰巧指纹还能对上，面试会被问穿。
  4. 相邻窗高度重叠，却每次 substring + 全量重排，没有「删左加右」的增量更新——这才是本题该练的肌肉。

小结：会判异位词，不会用定长窗 + 频次差；和 7/27 的 49、今日的 3 比，缺的是「窗口只动两端」的模板，不是题意理解。

最佳题解 ​

定长滑窗 + 26 桶计数（差分数 / 匹配数均可）。下面用「还差多少种字符对得上」的写法：

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

  const need = new Array(26).fill(0);
  const win = new Array(26).fill(0);
  const code = (ch) => ch.charCodeAt(0) - 97;

  for (let i = 0; i < m; i++) need[code(p[i])]++;

  const res = [];
  let differ = 0;
  for (let i = 0; i < 26; i++) {
    if (need[i] !== 0) differ++;
  }

  const add = (ch) => {
    const c = code(ch);
    win[c]++;
    if (win[c] === need[c]) differ--;
    else if (win[c] === need[c] + 1) differ++;
  };
  const remove = (ch) => {
    const c = code(ch);
    if (win[c] === need[c]) differ++;
    else if (win[c] === need[c] + 1) differ--;
    win[c]--;
  };

  for (let i = 0; i < m; i++) add(s[i]);
  if (differ === 0) res.push(0);

  for (let i = m; i < n; i++) {
    add(s[i]);
    remove(s[i - m]);
    if (differ === 0) res.push(i - m + 1);
  }
  return res;
};

更短的等价写法：维护两个长度 26 的数组，每次右进左出后 every/for 比是否全等（或预先算好「完全匹配时的签名」）。

  • 时间 O(n + |Σ|)，空间 O(|Σ|)（|Σ|=26）。
  • 为何更优：每个字符进出窗口各一次；不再对每窗排序。

关联题目 ​

题为何相关
242. 有效的字母异位词单次异位词判定，计数热身
49. 字母异位词分组排序/计数指纹；你 7/27 做过
567. 字符串的排列438 的「是否存在」版，同一模板
3. 无重复字符的最长子串今日第一题；同属滑窗，约束不同

一句话带走 ​

定长异位词子串：窗长固定，进一出一更新 26 计数，相等就记下起点——别对每个窗口排序。