0438. 找到字符串中所有字母异位词
大约 2 分钟
0438. 找到字符串中所有字母异位词
- 标签:哈希表、字符串、滑动窗口
- 难度:中等
题目大意
给定两个字符串 s
和 p
。
要求:找到 s
中所有 p
的异位词的子串,返回这些子串的起始索引。不考虑答案输出的顺序。
- 异位词:指由相同字母重排列形成的字符串(包括相同的字符串)。
解题思路
维护一个固定长度为 len(p)
的滑动窗口。于是问题的难点变为了如何判断 s
的子串和 p
是异位词。可以使用两个字典来分别存储 s
的子串中各个字符个数和 p
中各个字符个数。如果两个字典对应的键值全相等,则说明 s
的子串和 p
是异位词。但是这样每一次比较的操作时间复杂度是 ,我们可以通过在滑动数组中逐字符比较的方式来减少两个字典之间相互比较的复杂度,并用 valid
记录经过验证的字符个数。整个算法步骤如下:
- 使用哈希表
need
记录p
中各个字符出现次数。使用字典window
记录s
的子串中各个字符出现的次数。使用数组res
记录答案。使用valid
记录s
的子串中经过验证的字符个数。使用window_size
表示窗口大小,值为len(p)
。使用两个指针left
、right
。分别指向滑动窗口的左右边界。 - 一开始,
left
、right
都指向0
。 - 如果
s[right]
出现在need
中,将最右侧字符s[right]
加入当前窗口window
中,记录该字符个数。并验证该字符是否和need
中个对应字符个数相等。如果相等则验证的字符个数 +1,即valid += 1
。 - 如果该窗口字符长度大于等于
window_size
个,即right - left + 1 >= window_size
。则不断右移left
,缩小滑动窗口长度。- 如果验证字符个数
valid
等于窗口长度window_size
,则s[left, right + 1]
为p
的异位词,所以将left
加入到答案数组中。 - 如果
s[left]
在need
中,则更新窗口中对应字符的个数,同时维护valid
值。
- 如果验证字符个数
- 右移
right
,直到right >= len(nums)
结束。 - 输出答案数组
res
。
代码
class Solution:
def findAnagrams(self, s: str, p: str) -> List[int]:
need = collections.defaultdict(int)
for ch in p:
need[ch] += 1
window = collections.defaultdict(int)
window_size = len(p)
res = []
left, right = 0, 0
valid = 0
while right < len(s):
if s[right] in need:
window[s[right]] += 1
if window[s[right]] == need[s[right]]:
valid += 1
if right - left + 1 >= window_size:
if valid == len(need):
res.append(left)
if s[left] in need:
if window[s[left]] == need[s[left]]:
valid -= 1
window[s[left]] -= 1
left += 1
right += 1
return res