LeetCode 438 找到字符串中所有字母异位词（Python 固定滑动窗口+字符计数解法）

LeetCode 438 找到字符串中所有字母异位词（Python 固定滑动窗口+字符计数解法）

刷题标签：#滑动窗口 #字符计数 #字符串 #中等难度
题目链接：LeetCode 438

一、题目描述

给定两个字符串 s 和 p，找到 s 中所有 p 的字母异位词的子串，返回这些子串的起始索引。不考虑答案输出的顺序。

名词解释：字母异位词

两个字符串字符种类、每个字符出现次数完全一致，仅字符排列顺序不同，互为字母异位词。
例：ab 与 ba、abc 与 cba 都是异位词。

示例

示例 1

输入: s = "cbaebabacd", p = "abc"
输出: [0,6]
解释:
起始索引等于 0 的子串是 "cba"，它是 "abc" 的异位词。
起始索引等于 6 的子串是 "bac"，它是 "abc" 的异位词。

示例 2

输入: s = "abab", p = "ab"
输出: [0,1,2]
解释:
起始索引 0 → "ab"、索引 1 → "ba"、索引 2 → "ab"，均为 "ab" 的异位词。

提示

• 0 <= s.length <= 5 * 10^4
• s 由英文字母、数字、符号和空格组成（本题仅考虑小写英文字母）
• 异位词一定长度相等，因此只需在 s 中截取长度等于 len(p) 的连续子串判断。

二、前置核心概念

1. 固定大小滑动窗口

滑动窗口是字符串/数组刷题常用技巧，分为变长窗口和定长窗口：

• 本题使用固定窗口：窗口宽度 = 短字符串 p 的长度，窗口只能整体向右逐格平移，大小永远不变。
• 比喻：把长字符串 s 看作一条长廊，窗户宽度固定，每次只向右挪一格，逐段检查窗口内内容。

2. 字符计数数组

题目仅包含 26 个小写英文字母，我们用长度为 26 的数组统计字符出现次数：

• 映射规则：字母下标 = ord(字符) – ord('a')，实现 a→0、b→1 … z→25
• 优势：字符查找、计数修改时间复杂度为 $O(1)$，效率远高于字符串排序。

三、解题思路整体分析

思路1：暴力排序（仅入门理解，大数据超时）

缺点：每次截取+排序，时间复杂度高，字符串较长时会超时，仅适合理解题意。

思路2：滑动窗口 + 字符计数（最优解，面试/刷题首选）

优点：仅遍历一次字符串，时间复杂度 $O(n)$，可通过所有测试用例。

四、解法一：暴力排序法（入门版）

完整代码

class Solution(object):
def findAnagrams(self, s, p):
res = []
len_s = len(s)
len_p = len(p)

# 边界：模板更长，直接返回空
if len_p > len_s:
return res

# 将p排序，作为比对标准
p_sort = sorted(p)
# 遍历所有合法起始位置
for i in range(len_s – len_p + 1):
# 截取当前窗口子串并排序
sub_str = s[i:i+len_p]
if sorted(sub_str) == p_sort:
res.append(i)
return res

代码解读

优缺点

• ✅ 逻辑简单，新手易理解；
• ❌ 排序操作耗时，数据量大时超时，不适合工程使用。

五、解法二：滑动窗口 + 字符计数（最优解）

5.1 完整可运行代码

该版本为最终修正版，规避了数组职责混淆、循环嵌套、下标错误等常见坑点：

class Solution(object):
def findAnagrams(self, s, p):
"""
:type s: str
:type p: str
:rtype: List[int]
"""
res = []
len_s = len(s)
len_p = len(p)

# 边界判断：p比s长，无答案
if len_p > len_s:
return res

# 两个计数数组：win存模板p(基准，固定不变)，ts存s的滑动窗口(动态更新)
win = [0] * 26
ts = [0] * 26

# 第一步：初始化统计 p 和 s 的第一个窗口
for i in range(len_p):
# 统计模板 p 的字符次数
char_p = p[i]
index = ord(char_p) – ord("a")
win[index] += 1

# 统计 s 第一个窗口的字符次数
char_s = s[i]
index1 = ord(char_s) – ord("a")
ts[index1] += 1

# 检查第一个窗口是否匹配
if win == ts:
res.append(0)

# 第二步：窗口持续向右滑动
for i in range(len_p, len_s):
# 1. 左侧字符滑出窗口，窗口计数-1
char_left = s[i – len_p]
index2 = ord(char_left) – ord("a")
ts[index2] -= 1

# 2. 右侧新字符滑入窗口，窗口计数+1
char_right = s[i]
index3 = ord(char_right) – ord("a")
ts[index3] += 1

# 两数组完全相等，说明当前窗口是异位词
if win == ts:
res.append(i – len_p + 1)

return res

5.2 逐行代码详解

1. 基础变量与边界判断

res = []
len_s = len(s)
len_p = len(p)

if len_p > len_s:
return res

• res：结果列表，存储所有符合条件的窗口起始下标；
• len_s / len_p：分别记录两个字符串长度；
• 边界兜底：若模板 p 更长，直接返回空列表。

2. 初始化26位字符计数数组

win = [0] * 26
ts = [0] * 26

• [0] * 26：生成长度为26、初始值全为0的数组，对应 a~z 26个小写字母；
• win：基准数组，仅统计模板 p，初始化后全程不修改；
• ts：窗口数组，统计 s 中当前窗口的字符，窗口移动时动态修改。

3. 初始化首个窗口

for i in range(len_p):
char_p = p[i]
index = ord(char_p) – ord("a")
win[index] += 1

char_s = s[i]
index1 = ord(char_s) – ord("a")
ts[index1] += 1

• 循环次数 = 窗口宽度 len(p)，一次性完成模板p和s首个窗口的字符统计；
• ord(字符) – ord("a")：核心映射公式，将字母转为 0~25 的数组下标；
• 数组[下标] += 1：对应字符出现次数 +1。

4. 检查首个窗口

if win == ts:
res.append(0)

• 两个计数数组完全一致 → 首个窗口是异位词，记录起始下标 0；
• 该判断必须放在循环外，避免逐个统计字符时重复判断。

5. 窗口滑动核心逻辑

for i in range(len_p, len_s):
# 左侧字符滑出
char_left = s[i – len_p]
index2 = ord(char_left) – ord("a")
ts[index2] -= 1

# 右侧字符滑入
char_right = s[i]
index3 = ord(char_right) – ord("a")
ts[index3] += 1

if win == ts:
res.append(i – len_p + 1)

• 循环范围：从 len_p 开始遍历，逐个处理新进入窗口的字符；
• 固定公式1：i – len_p → 被窗口挤出的左侧字符下标；
• 固定公式2：i – len_p + 1 → 当前窗口的起始下标；
• 规则：窗口移动只修改窗口数组 ts，基准数组 win 保持不变。

6. 返回结果

return res

遍历完成后，返回所有合法下标。

5.3 实战流程演示（示例：s = "abab", p = "ab"）

字符串下标：s[0]=a、s[1]=b、s[2]=a、s[3]=b，窗口宽度 len_p=2

六、复杂度分析

1. 暴力排序法

• 时间复杂度：$O(N\cdot K\log K)$，$N$ 为 s 长度，$K$ 为 p 长度（每次排序耗时 $K\log K$）；
• 空间复杂度：$O(K)$，存储排序后的字符串。

2. 滑动窗口+字符计数（最优解）

• 时间复杂度：$O(N)$，仅遍历一次字符串，26位数组对比为常数操作；
• 空间复杂度：$O(1)$，两个固定长度为26的数组，空间不随输入变化。

七、刷题高频踩坑总结（新手必看）

结合调试过程中遇到的问题，整理最容易出错的5个点：

八、总结与同类题型推荐

知识点总结

同类刷题推荐