心路历程:
看到这个类型的题总以为要用动态规划去做,结果想了半天递推关系没想出来。
看来决定一道题是否适合动态规划不能只按照这道题长得像不像要用动态规划的标准,而应该看重叠子问题现象是否明显。
这道题本质在考察计数集合的用法,可以用sort,也可以用Counter,实测发现Counter的时间复杂度低一点
注意的点:
1、Counter的对象可以直接用==进行比较,且比sort要快速一些。
2、数组的长度 = 数组end索引 - 数组start索引 + 1,简记为数组长度等于索引差加一,方便下次能快速分析边界条件而不用犹豫。
解法:遍历
class Solution:
def findAnagrams(self, s: str, p: str) -> List[int]:
from collections import Counter
# pset = sorted(p)
pset = Counter(p)
l = len(p)
res = []
for i in range(len(s) - l + 1):
c = Counter(s[i:i+l])
if c == pset: # Counter的计数对象是可以直接比较的
# if sorted(s[i:i+l]) == pset:
res.append(i)
return res