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

题解思路

本题是一个滑动窗口问题，要求找出所有 p 的异位词（即字符相同但顺序不同的子串）在 s 中的起始索引。

1. 使用固定大小的滑动窗口

由于 p 的所有异位词长度固定为 len(p)，可以使用固定大小的滑动窗口遍历 s。

• 维护一个 p 的字符计数 p_count（字典或数组）。
• 维护一个 s 的窗口 s_count，长度等于 p，表示当前窗口中的字符频率。

Leetcode 9.找到字符串中所有字母异位词-原题链接

题目内容

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

输入描述

输入共两行。

• 第一行为字符串$s$

• 第二行为字符串$p$

输出描述

输出为一行，包含所有满足条件的子串的起始索引，索引之间用空格分隔。索引的顺序可以是任意的，但必须包含所有符合条件的索引。

样例1

输入

cbaebabacd
abc

输出

0 6

说明

起始索引等于 $0$的子串是 "$cba$", 它是 "$abc$" 的异位词。 起始索引等于 $6$的子串是 "$bac$", 它是 "$abc$" 的异位词。

样例2

输入

abab
ab

输出

0 1 2

说明

起始索引等于 $0$ 的子串是 "$ab$", 它是 "$ab$" 的异位词。

起始索引等于 $1$ 的子串是 "$ba$", 它是 "$ab$" 的异位词。

起始索引等于 $2$ 的子串是 "$ab$", 它是 "$ab$" 的异位词。

提示

• $1 <= s.length, p.length <= 3 * 10^4$
• $s$和 $p$仅包含小写字母