AnyJohn 的网络博客

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

Properties1
tags算法, 中等, 滑动窗口, leetcode

6分钟阅读

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

Origin: LeetCode 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” 的异位词。
  • 起始索引等于 2 的子串是 “ab”，它是 “ab” 的异位词。

提示：

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

我的解法（排序比较·暴力版）

function findAnagrams(s: string, p: string): number[] {
    if (p.length > s.length) return [];
    const str = p.split('').sort().join('')
    const result: number[] = []
    for (let i = 0; i < s.length; i++) {
        let j = i + p.length - 1
        if (j < s.length) {
            const subStr = s.substring(i, j + 1)
            if (subStr.split('').sort().join('') === str) {
                result.push(i)
            }
        } else {
            break
        }
    }
    return result
};

思路：p 排序后作为”异位词指纹”，逐个窗口取子串排序对比。本地 5 组用例验证通过（含 [0,6]、[0,1,2]、边界 [“aa”,“a”]），但 LeetCode 提交未 AC。

问题：每个窗口都重新排序，窗口之间没有信息复用。"cbaebabacd" 挪一格，窗口里 9 个字符的排序结果和上一个窗口毫无关系——但其中 2/3 的字符其实是共用的。

状态：未 AC。明天做滑动窗口优化版后统一更新此笔记。

解题思路（草稿）

和第 3 题的区别

第 3 题：窗口维护”无重复”，长度可变，left 被重复逼着收缩。 本题：窗口长度固定为 p.length，在所有固定窗口里挑”字符组成 = p”的。

所以模板变形：

第 3 题:  right 扩张 → 有重复就收缩 left → 过程中随时记录 max
本  题:  right 扩张 → 窗口超过 p.length 就缩一格 → 窗口恰好等于 p.length 时检查是否异位词

不变量从”无重复”变成了”窗口大小 ≤ p.length”。

判断异位词：计数比较

两个 Map（或 26 长度数组）记录窗口内字符计数和 p 的字符计数，逐个比较。

优化：不用每次都比较 26 个字母——维护一个 matched 变量记录”已匹配的字母种数”，进出窗口时动态加减，matched === 26（或 p 的种数）就是异位词。但这会增加出 bug 的面（进窗口+1 后可能从 0 变 1 也可能从需要的数变成超了），第一版先写朴素的逐个比较，ac 了再优化。

朴素版草稿

function findAnagrams(s: string, p: string): number[] {
    const result: number[] = []
    const need = new Map<string, number>()
    for (const c of p) need.set(c, (need.get(c) ?? 0) + 1)
    const window = new Map<string, number>()
 
    const matches = (a: Map<string, number>, b: Map<string, number>) => {
        if (a.size !== b.size) return false
        for (const [k, v] of b) if (a.get(k) !== v) return false
        return true
    }
 
    for (let right = 0; right < s.length; right++) {
        // 扩张
        const c = s[right]
        window.set(c, (window.get(c) ?? 0) + 1)
        // 窗口超长，缩一格
        if (right - left + 1 > p.length) {
            const d = s[left]
            window.set(d, window.get(d)! - 1)
            if (window.get(d) === 0) window.delete(d)   // 保持 size 比较有效
            left++
        }
        // 恰好等长时检查
        if (right - left + 1 === p.length && matches(window, need)) {
            result.push(left)
        }
    }
    return result
}

注意 window.delete(d)：计数减到 0 要删 key，否则 window.size 会比 need.size 大，matches 的 size 预检失效。

复杂度对比

  • 朴素版：O(n × 26)，每次检查 26 个字母（Map 版是 O(n × distinct)）
  • matched 优化版：O(n)，真·每步 O(1)

复杂度

  • 时间：O(n × |Σ|)，|Σ| 是字符集大小（小写字母 26）
  • 空间：O(|Σ|)

关联

    1. 无重复字符的最长子串 - 可变窗口版，本题为固定窗口
    1. 字符串的排列 - 和本题几乎一样，返回值从索引数组变成布尔
    1. 最小覆盖子串 - 可变窗口 + 计数匹配的完全体

关系图谱

近期发布