找到字符串中所有字母异位词
给定两个字符串 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" 的异位词。
首次提交
想法
首先使用sorted()将字符串p排序，滑动大小为与p长度相同的窗口，当窗口中排序的字符串与排序后的字符串p相同时，记录下位置，最后输出。
class Solution:
def findAnagrams(self, s: str, p: str) -> List[int]:
target = sorted(p)
result = []
for i in range(len(s)-len(p)+1):
temp = sorted(s[i:i+len(p)])
if target == temp:
result.append(i)
return result 时间复杂度
- 排序部分：
- 每次对长度为 $m$ 的子串调用
sorted()排序，时间复杂度为 $O(m \log m)$。 - 遍历 $s$ 时，总共需要执行$n – m + 1 \approx n$ 次排序，因此排序部分的总时间复杂度为: $O(n \cdot m \log m)$
- 每次对长度为 $m$ 的子串调用
- 整体复杂度：
- 对于每个窗口的处理，排序操作占据主要计算量，所以总体时间复杂度为: $O(n \cdot m \log m)$
空间复杂度
- 每次排序会创建一个长度为 $m$ 的子串的副本用于排序，占用 $O(m)$ 的额外空间。
- 因此，空间复杂度为：$O(m)$
改进方法：
改进想法
将p创建字典，key为string中的字符，值为出现的次数。从头开始遍历字符串滑动与p相同大小的窗口，首先根据第一个窗口内的所有字符同理创建一个字典，判断两个字典是否相同，相同就保存索引，接下来将最左边的索引对应的字符对应的值从字典中减一，滑动窗口，最右边索引对应的值加一，再次与p的字典进行比较
class Solution:
def findAnagrams(self, s: str, p: str) -> List[int]:
p_dict = {} # 根据字符串p初始化字典
result = []
# 遍历字符串，如果当前字符是字典的key，则对应值+1，否则添加key并将值设为1
for item in p:
if item in p_dict:
p_dict[item] += 1
else:
p_dict[item] = 1
# 同理创建一个滑块中的字符串对应的字典
temp = {}
# 首先将最左边索引为0的滑块中的字符串放入字典
for item in s[:len(p)]: # 注意使用切片[:]，而不是索引[]
if item in temp:
temp[item] += 1
else:
temp[item] = 1
# 判断当前滑块字典是否与p字典相同
if temp == p_dict:
result.append(0)
# 滑动滑块，从字典中减去上一步最左边的字符，
# 加上滑动后最右边的字符，再与字典p进行比较(可优化)
for i in range(1, len(s)-len(p)+1):
# 减去上一步最左边的字符，由于删去字符对应的值时可能为0，
# 而为0的值对应的key需删去
if temp[s[i-1]] - 1 == 0:
del(temp[s[i-1]])
else:
temp[s[i-1]] -= 1
# 加上滑动后最右边的字符
# 注意索引，当最左边的索引为0时，最右边索引为len(p)-1
if s[i+len(p)-1] in temp:
temp[s[i+len(p)-1]] += 1
else:
temp[s[i+len(p)-1]] = 1
# 与字典p进行比较
if temp == p_dict:
result.append(i)
return result
时间复杂度分析
- 初始化
p_dict和第一个窗口的temp，需要遍历 ppp 和第一个窗口的字符，总耗时 $O(m)$。 - 滑动窗口的更新和比较，需要遍历 $s$ 的长度，总共滑动 $n – m + 1$ 次，每次更新和比较的操作为 $O(1)$。
- 总时间复杂度：$O(n)$，其中 $n = \text{len}(s)$，$m = \text{len}(p)$。
空间复杂度分析
- 需要两个字典存储字符频率，每个字典的大小与字符串 ppp 的字符种类数有关，因此空间复杂度为 $O(m)$。
最终方法
优化点
- 字典初始化：当前的
p_dict和temp初始化过程中，使用了显式判断if item in dict，可以用collections.defaultdict简化： - 删除键的优化：在删除键时，显式检查了值是否为 0，可以使用
defaultdict自动避免未定义键的访问错误，进一步简化处理。 - 减少比较操作：当前代码中每次滑动窗口后都会比较
temp == p_dict。如果在更新temp时同时记录匹配字符的数量，可以避免频繁的字典比较，进一步提升效率。
from collections import defaultdict
p_dict = defaultdict(int)
temp = defaultdict(int)
for item in p:
p_dict[item] += 1
for item in s[:len(p)]:
temp[item] += 1代码
from collections import defaultdict
class Solution:
def findAnagrams(self, s: str, p: str) -> List[int]:
p_dict = defaultdict(int)
temp = defaultdict(int)
result = []
for item in p:
p_dict[item] += 1
for item in s[:len(p)]:
temp[item] += 1
for i in range(len(s)-len(p)):
if temp == p_dict:
result.append(i)
temp[s[i]] -= 1
if temp[s[i]] == 0:
del(temp[s[i]])
temp[s[i+len(p)]] += 1
if temp == p_dict:
result.append(len(s)-len(p))
return result