LeetCode 438：找到字符串中所有字母异位词 | 滑动窗口

LeetCode 438：找到字符串中所有字母异位词 | 滑动窗口

引言

找到字符串中所有字母异位词（Find All Anagrams in a String）是 LeetCode 第 438 题，难度为 Medium。题目要求在字符串 s 中找到所有字符串 p 的字母异位词的起始索引。

字母异位词是指两个字符串包含相同字符但可能排列顺序不同。

算法实现

Python 实现

def findAnagrams(s, p): from collections import Counter need = Counter(p) window = {} left, right = 0, 0 valid = 0 result = [] while right < len(s): c = s[right] right += 1 if c in need: window[c] = window.get(c, 0) + 1 if window[c] == need[c]: valid += 1 while right - left >= len(p): if valid == len(need): result.append(left) d = s[left] left += 1 if d in need: if window[d] == need[d]: valid -= 1 window[d] -= 1 return result

复杂度分析

时间复杂度：O(n + m)
空间复杂度：O(m)

总结

滑动窗口同样适用于异位词问题，只需维护字符计数即可。