LeetCode热题100-找到字符串中所有字母异位词

给定两个字符串s和p找到s中所有p的异位词的子串返回这些子串的起始索引。不考虑答案输出的顺序。通过阅读题目首先想到的就是通过排序判断是否为异位词子串但是这提交会出超时时间复杂度较高O (n×m log m)class Solution: def findAnagrams(self, s: str, p: str) - List[int]: if not s: return [] def isequal(s1: str, s2: str): s1_tmp sorted(s1) s2_tmp sorted(s2) return s1_tmp s2_tmp res [] length len(p) i 0 while i len(s): right i length -1 if right 1 len(s) and isequal(s[i:right1], p): res.append(i) i 1 return res这里使用滑动窗口 哈希表计数因为只需要判断字符个数一致即为异位词所以只需要使用哈希表保证窗口内和给定p哈希表一致就说明一样这里使用普通的字典使用defaultdict比较方便因为会自动初始化为0省去判断字典是否存在。class Solution: def findAnagrams(self, s: str, p: str) - List[int]: len_s len(s) len_p len(p) if len_s len_p: return [] p_dict, w_dict {}, {} for c in p: if c in p_dict: p_dict[c] 1 continue p_dict[c] 1 for c in s[:len_p]: if c in w_dict: w_dict[c] 1 continue w_dict[c] 1 res [] if w_dict p_dict: res.append(0) for i in range(len_p, len_s): left_char s[i - len_p] w_dict[left_char] - 1 if w_dict[left_char] 0: del w_dict[left_char] right_char s[i] if right_char in w_dict: w_dict[right_char] 1 else: w_dict[right_char] 1 if w_dict p_dict: res.append(i - len_p 1) return resfrom collections import defaultdict class Solution: def findAnagrams(self, s: str, p: str) - List[int]: len_s len(s) len_p len(p) if len_s len_p: return [] p_dict, w_dict defaultdict(int), defaultdict(int) for c in p: p_dict[c] 1 for c in s[:len_p]: w_dict[c] 1 res [] if w_dict p_dict: res.append(0) for i in range(len_p, len_s): left_char s[i - len_p] w_dict[left_char] - 1 if w_dict[left_char] 0: del w_dict[left_char] right_char s[i] w_dict[right_char] 1 if w_dict p_dict: res.append(i - len_p 1) return res