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

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

方法一：哈希表

class Solution(object): def findAnagrams(self, s, p): result={} result["".join(sorted(p))]=[] for i in range(len(s)-len(p)+1): t=s[i:i+len(p)] if "".join(sorted(t)) in result: result["".join(sorted(p))].append(i) return result["".join(sorted(p))]

方法二：滑动窗口

滑动一次，判断一次

class Solution(object): def findAnagrams(self, s, p): p_char=[0]*26 s_char=[0]*26 result=[] if len(p)>len(s): return result for _ in range(len(p)): p_char[ord(p[_])-ord("a")]+=1 s_char[ord(s[_])-ord("a")]+=1 if p_char==s_char: result.append(0) for i in range(len(s)-len(p)): s_char[ord(s[i])-ord("a")]-=1 s_char[ord(s[i+len(p)])-ord("a")]+=1 if p_char==s_char: result.append(i+1) return result