找到字符串中所有字母异位词
1、题目描述
给定两个字符串 s 和 p，找到 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 * 104s和p仅包含小写字母
2、题解
2.1 滑动窗口
据题目要求，我们需要在字符串 s 寻找字符串 p 的异位词。因为字符串 p 的异位词的长度一定与字符串 p 的长度相同，所以我们可以在字符串 s 中构造一个长度为与字符串 p 的长度相同的滑动窗口，并在滑动中维护窗口中每种字母的数量；当窗口中每种字母的数量与字符串 p 中每种字母的数量相同时，则说明当前窗口为字符串 p 的异位词。
在算法的实现中，我们可以使用数组来存储字符串 p 和滑动窗口中每种字母的数量。
当字符串 s 的长度小于字符串 p 的长度时，字符串 s 中一定不存在字符串 p 的异位词。但是因为字符串 s 中无法构造长度与字符串 p 的长度相同的窗口，所以这种情况需要单独处理。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35public class Solution {
public List<Integer> findAnagrams(String s, String p) {
int sLen = s.length(), pLen = p.length();
if (sLen < pLen) {
return new ArrayList<Integer>();
}
List<Integer> ans = new ArrayList<Integer>();
// 建立两个数组存放字符串中字母出现的词频，并以此作为标准比较，每个索引对应的值，为该字母出现的次数，初始次数都是0
int[] sCount = new int[26];
int[] pCount = new int[26];
// 当滑动窗口的首位在s[0]处时 （相当于放置滑动窗口进入数组）
// 按照p字符数组的长度去遍历
for (int i = 0; i < pLen; i++) {
++sCount[s.charAt(i) - 'a']; // 记录s中前pLen个字母的词频
++pCount[p.charAt(i) - 'a']; // 记录要寻找的字符串中每个字母的词频(只用进行一次来确定)
}
// 判断放置处是否有异位词。若相等，则表明s的前几位就是p的异位词。起始索引即为0.
if (Arrays.equals(sCount, pCount)) {
ans.add(0);
}
// 开始让窗口进行滑动
for (int i = 0; i < sLen - pLen; ++i) {
--sCount[s.charAt(i) - 'a']; // 将滑动前首位的词频删去
++sCount[s.charAt(i + pLen) - 'a']; // 增加滑动后最后一位的词频（以此达到滑动的效果）
// 完成了一次滑动窗口
// 若相等，存在异位词，起始索引为i+1
if (Arrays.equals(sCount, pCount)) {
ans.add(i + 1);
}
}
return ans;
}
}1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25class Solution:
def findAnagrams(self, s: str, p: str) -> List[int]:
s_len, p_len = len(s), len(p)
if s_len < p_len:
return []
ans = []
s_count = [0] * 26
p_count = [0] * 26
for i in range(p_len):
s_count[ord(s[i]) - 97] += 1
p_count[ord(p[i]) - 97] += 1
if s_count == p_count:
ans.append(0)
for i in range(s_len - p_len):
s_count[ord(s[i]) - 97] -= 1
s_count[ord(s[i + p_len]) - 97] += 1
if s_count == p_count:
ans.append(i + 1)
return ans复杂度分析
时间复杂度：O(m+(n−m)×Σ)，其中 n 为字符串 s 的长度，m 为字符串 p 的长度，Σ 为所有可能的字符数。我们需要 O(m) 来统计字符串 p 中每种字母的数量；需要 O(m) 来初始化滑动窗口；需要判断 n−m+1 个滑动窗口中每种字母的数量是否与字符串 p 中每种字母的数量相同，每次判断需要 O(Σ) 。因为 s 和 p 仅包含小写字母，所以 Σ=26。
空间复杂度：O(Σ)。用于存储字符串 p 和滑动窗口中每种字母的数量。