LeetCode_0438_中等_找到字符串中所有字母异位词.md

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

问题简述

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

---

思路 1: 定长滑动窗口

• 简单来说, 就是在滑动窗口移动的过程中更新一个 字符字典 与 p 比较, 数量完全匹配的话就进行记录;
• 利用 Counter 简化统计代码

Python

class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        
        from collections import Counter

        ans = []
        lp = len(p)
        cp = Counter(p)
        cs = Counter(s[:lp - 1])
        for r in range(lp - 1, len(s)):
            cs[s[r]] += 1
            l = r - lp + 1

            if cp == cs:
                ans.append(l)
                
            cs[s[l]] -= 1
            if cs[s[l]] == 0:   # 删除数量为 0 的字母
                del cs[s[l]]
        
        return ans

---

思路 2: 不定长滑动窗口

两种方法: 定长滑窗/不定长滑窗 - 灵茶山艾府

---

算法笔记

• 滑动窗口模板

其他算法笔记

• 二分查找相关
• 从递归到递推 (动态规划)
• 树形递归技巧
• 链表操作备忘

---

相关问题

LeetCode Hot 100 (32)

[中等, LeetCode] 三数之和 🔥
[中等, LeetCode] 下一个排列 🔥
[中等, LeetCode] 两数相加 🔥
[中等, LeetCode] 全排列 🔥
[中等, LeetCode] 全排列II 🔥
[中等, LeetCode] 删除链表的倒数第N个结点 🔥
[中等, LeetCode] 和为K的子数组 🔥
[中等, LeetCode] 在排序数组中查找元素的第一个和最后一个位置 🔥
[中等, LeetCode] 字母异位词分组 🔥
[中等, LeetCode] 括号生成 🔥
[中等, LeetCode] 搜索旋转排序数组 🔥
[中等, LeetCode] 数组中的第K个最大元素 🔥
[中等, LeetCode] 无重复字符的最长子串 🔥
[中等, LeetCode] 最长回文子串 🔥
[中等, LeetCode] 最长连续序列 🔥
[中等, LeetCode] 电话号码的字母组合 🔥
[中等, LeetCode] 盛最多水的容器 🔥
[中等, LeetCode] 组合总和 II 🔥
[中等, LeetCode] 组合总和 🔥

[困难, LeetCode] K个一组翻转链表 🔥
[困难, LeetCode] 合并K个升序链表 🔥
[困难, LeetCode] 寻找两个正序数组的中位数 🔥
[困难, LeetCode] 接雨水 🔥
[困难, LeetCode] 最小覆盖子串 🔥
[困难, LeetCode] 最长有效括号 🔥
[困难, LeetCode] 正则表达式匹配 🔥
[困难, LeetCode] 滑动窗口最大值 🔥
[困难, 牛客] 最小覆盖子串 🔥

[简单, LeetCode] 两数之和 🔥
[简单, LeetCode] 合并两个有序链表 🔥
[简单, LeetCode] 有效的括号 🔥
[简单, LeetCode] 移动零 🔥

滑动窗口 (7)

[中等, LeetCode] 无重复字符的最长子串 🔥
[中等, 牛客] 最长无重复子数组

[困难, LeetCode] 最小覆盖子串 🔥
[困难, 剑指Offer] 滑动窗口的最大值
[困难, 牛客] 数组中的最长连续子序列
[困难, 牛客] 最小覆盖子串 🔥

[简单, 牛客] 压缩字符串(一)