哈希分组与窗口频数

如何把字母异位词分组？

• 特征: 互为字母异位词的字符串排序后得到同一个字符串;
• 分组 key: 排序后的字符串;
• 分组 value: 原始字符串列表;
• 复杂度: 时间 O(n × k log k), k 为字符串长度; 空间 O(n × k);

function groupAnagrams(strs: string[]): string[][] {
  const hash = new Map<string, string[]>();
  for (const str of strs) {
    const key = str.split("").sort().join("");
    const group = hash.get(key) ?? [];
    group.push(str);
    hash.set(key, group);
  }
  return [...hash.values()];
}

如何找出字符串中所有字母异位词的起始下标？

• 目标: 在 s 中找出所有与 p 互为字母异位词的子串;
• 窗口: 固定长度 p.length 的滑动窗口;
• 频数表: 分别记录 p 与当前窗口的字符频数;
• 判定: 窗口长度足够时比较两张频数表, 一致则记录窗口左端点;
• 移动: 右指针前进一位的同时, 左指针出窗并把该字符频数减一;
• 复杂度: 时间 O(n × 字符集大小), 空间 O(字符集大小);

function findAnagrams(s: string, p: string): number[] {
  const pHash = new Map<string, number>();
  for (const ch of p) pHash.set(ch, (pHash.get(ch) ?? 0) + 1);

  const result: number[] = [];
  const sHash = new Map<string, number>();
  let left = 0;
  let right = 0;

  while (right < s.length) {
    sHash.set(s[right], (sHash.get(s[right]) ?? 0) + 1);

    if (right - left + 1 < p.length) {
      right++;
      continue;
    }

    let matched = true;
    for (const [ch, count] of pHash) {
      if (sHash.get(ch) !== count) {
        matched = false;
        break;
      }
    }
    if (matched) result.push(left);

    sHash.set(s[left], (sHash.get(s[left]) ?? 0) - 1);
    left++;
    right++;
  }

  return result;
}

• 窗口维护的关键: 窗口只前进不回退, 出窗时同步撤销左端字符的频数贡献;