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

Difficulty
Medium
Tags
滑动窗口
双指针
Star
给定两个字符串 sp,找到 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 * 104
  • sp 仅包含小写字母

滑动窗口

思路
类似
🧽
567. 字符串的排列
,只不过本题目是要收集所有符合条件的字串起始位置,其实就是满足条件的窗口的left
根据不同的收缩条件,有两种写法
题解
class Solution: def findAnagrams(self, s: str, p: str) -> List[int]: need = collections.defaultdict(int) window = collections.defaultdict(int) for c in p: need[c] += 1 left, right = 0, 0 valid = 0 res = [] while right < len(s): cur = s[right] right += 1 if cur in need: window[cur] += 1 if window[cur] == need[cur]: valid += 1 if right - left >= len(p): if valid == len(need): res.append(left) dele = s[left] left += 1 if dele in need: if window[dele] == need[dele]: valid -= 1 window[dele] -= 1 return res # --------- class Solution: def findAnagrams(self, s: str, p: str) -> List[int]: if len(p) > len(s): return [] target = collections.Counter(p) res = [] wds = collections.defaultdict(int) l, r = 0, 0 valid = 0 while r < len(s): cur_char = s[r] r += 1 if cur_char in target: wds[cur_char] += 1 if wds[cur_char] == target[cur_char]: valid += 1 while valid == len(target): if r - l == len(p): res.append(l) delet_char = s[l] l += 1 if delet_char in target: wds[delet_char] -= 1 if wds[delet_char] < target[delet_char]: valid -= 1 return res
关于收缩窗口位置的if while,
  • 如果是用窗口大小来做条件的话,即 right - left ≥ len(p),if 就可以
  • 但如果是用valid做条件的话,必须要用while.