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

Leetcode Link: 438. 找到字符串中所有字母异位词 - 力扣（LeetCode） (leetcode-cn.com)

题目

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

异位词 指由相同字母重排列形成的字符串（包括相同的字符串）。

 

解法一

思路：滑动窗口法，同样维护一个need变量来表示窗口内信息

题解：

class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
	    # 特殊情况
        if len(p) > len(s):
            return []
            
        res = []  # 结果  
        need = collections.defaultdict(int) # 窗口信息，用need维护
        need_cnt = 0  # 需求计数变量，同样只有need[c]>0才是必需元素
	    # 初始化 need
        for c in p:
            need_cnt += 1
            need[c] += 1
	    # 初始化窗口左右边界位置，这里左开右闭
        left = 0
        right = 0
        while(right<len(s)):
            ### 入窗
            rc = s[right]
            if need[rc] > 0: # >0 表示必需元素，拿到了一个必需的，因此 cnt-1
                need_cnt -= 1
            need[rc] -= 1 # 对应的需要也 -1
            right += 1 # 有边界增加
            ### 出窗判断
            while(right - left > len(p)): # 要保证窗宽度和len(p)一样，小了不用缩，大了就要缩。其实等价于窗宽度=len(p)时左右都动
                lc = s[left]
                need[lc] += 1
                if need[lc] > 0: # 这里仔细想想，只有移出去了>0才表示现在该需要这个了，所以在这里 cnt + 1
                    need_cnt += 1
                left += 1
            if need_cnt == 0: # 如果现在没需要了，说明满足条件了。
                res.append(left) 
        return res
                

解法二

思路 字符串，比较特殊，用 list 做计数用的结构，比较当前和目标是不是相等即可。

感觉比解法一更好理解。

题解

class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        target = [0]*26
        cur = [0]*26
        for c in p:
            idx = ord(c)-ord('a')
            target[idx] += 1
        
        left = 0
        right = 0
 
        res = []
        while(right < len(s)):
            idx = ord(s[right])-ord('a')
            cur[idx] += 1
 
            while(right-left+1>len(p)):
                cur[ord(s[left])-ord('a')] -= 1
                left += 1
            
            if cur == target:
                res.append(left)
 
            right += 1
        return res
 

启发和联系

用 while 感觉思路会更清晰，明确的控制窗口的边界的变化。 感觉缩窗用一个 while 来控制也行 主要是想清楚 need 和 need_cnt 什么时候变化，以及need中的必需元素是什么。