Skip to content

Latest commit

 

History

History
105 lines (85 loc) · 4.9 KB

09_滑动窗口_中等_0438_找到字符串中所有字母异位词_230824.md

File metadata and controls

105 lines (85 loc) · 4.9 KB
Raw

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

  • 标签：哈希表、字符串、滑动窗口
  • 难度：中等

题目大意

给定两个字符串 s 和 p。

要求：找到 s 中所有 p 的异位词的子串，返回这些子串的起始索引。不考虑答案输出的顺序。

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

解题思路

维护一个固定长度为 len(p) 的滑动窗口。于是问题的难点变为了如何判断 s 的子串和 p 是异位词。可以使用两个字典来分别存储 s 的子串中各个字符个数和 p 中各个字符个数。如果两个字典对应的键值全相等，则说明 s 的子串和 p 是异位词。但是这样每一次比较的操作时间复杂度是 $O(n)$，我们可以通过在滑动数组中逐字符比较的方式来减少两个字典之间相互比较的复杂度，并用 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

我自己写的实现

class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        # 初始化目标字符串与滑动窗口的哈希表，字符做键，字符个数做值
        need, window = defaultdict(int), defaultdict(int)
        # 将给定字符串的属性赋值到已经初始化好的哈希表中
        for c in p:
            need[c] += 1
        # 初始化快慢指针，覆盖程度与返回值
        left, right = 0, 0 
        valid = 0
        res = []

        # 判断是否还需要进行窗口滑动
        while right < len(s):
            c = s[right] # c是要加进窗口的字符
            right += 1 # 扩大窗口
            # 进行窗口内一系列数据的更新
            if c in need:
                window[c] += 1
                if window[c] == need[c]:
                    valid += 1
            # 判断左侧窗口是否需要收缩（窗口的长度大于给定p的长度）
            while right - left >= len(p):
                #  当串口符合条件时，将起始索引加入res
                if valid == len(need):
                    res.append(left)
                d = s[left] # d是将移出窗口的字符
                left += 1 # 增大左指针进行窗口收缩
                # 进行窗口内一系列数据的更新
                if d in need:
                    if window[d] == need[d]:
                        valid -= 1
                    window[d] -= 1

        return res

参考：我写了首诗，把滑动窗口算法算法变成了默写题 | labuladong 的算法小抄

复杂度分析

image-20230824173444380