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" 的异位词。
题解：滑动窗口
class Solution:
def findAnagrams(self, s: str, t: str) -> List[int]:
need={}# 存储字符串 t 中各个字符的需求量
window={}# 存储滑动窗口中各个字符的出现次数
for c in t:#遍历字符串t
need.setdefault(c,0)#访问不存在的键时自动创建并将值设置为 0
need[c]+=1# 统计字符串 t 中各个字符的需求量
left=0# 滑动窗口的左指针
right=0# 滑动窗口的右指针
valid=0# 记录满足需求的字符数
res=[]#结果列表
while right<len(s):
c=s[right]# 当前字符
right+=1# 右指针右移
if c in need:#当前字符是目标字符中的
window.setdefault(c,0)#访问不存在的键时自动创建并将值设置为 0
window[c]+=1# 更新滑动窗口中当前字符的出现次数
if window[c]==need[c]:
valid+=1# 如果滑动窗口中当前字符的出现次数达到需求量，增加满足需求的字符数
while valid==len(need):#每个字符的次数都达到了要求
if right-left==len(t):#数量也是相等的话
res.append(left)#把第一个索引的坐标加入结果列表
d=s[left]# 将要移出窗口的字符
left+=1# 左指针右移
if d in need:#当前字符是目标字符中的
if window[d]==need[d]:#如果滑动窗口中当前字符等于目标字符的值
valid-=1# 如果移出窗口的字符导致窗口不再满足需求，则减少满足需求的字符数
window[d]-=1# 更新滑动窗口中移出字符的出现次数
return res#返回结果列表