leetcode：找到字符串中所有字母异位词

 题目： 

        给定两s和p中所有p的异位词的子串，返回这些子串的起始索引。不考虑答案输出的顺序。异位词指由相同字母重排列形成的字符串（包括相同的字符串）。

示例 ：

输入	输出	解释
s = "cbaebabacd", p = "abc"	[0,6]	起始索引等于 0 的子串是 "cba", 它是 "abc" 的异位词。 起始索引等于 6 的子串是 "bac", 它是 "abc" 的异位词。

提示：

• 1<=s.length，p.length<=3*10^4
• s和p仅包含小写字母

相关标签：哈希、字符串、滑动窗口

题解：   

        根据题目中的提示，我们可以先统计出字符串p的个数，再for循环遍历统计字符串s的个数。利用滑动窗口来确定比较范围，字符串p的长度。如果统计个数相等，即是p的异位词。

注意：Counter统计个数为0的元素依旧存在，如果直接与p的统计个数比较是错误的，所以需要判断新元素是否在p里面，添加元素值为0。

代码：Python

import collectionss = "cbaebabacd"
p = "abc"def leetcode_fun1():'''1、滑动窗口，一次遍历2、异位词比较：计数元素个数'''n, m, pl, res = len(p), len(s), collections.Counter(p), list()if m < n:return []pro, pre = 0, n - 1while pre < m:if pl == collections.Counter(s[pro:pre + 1]):res.append(pro)pro += 1pre += 1return resdef leetcode_fun2():'''1、滑动窗口、一次遍历，异位词比较：计数元素个数'''res, n, m = list(), len(p), len(s)cnt_p = collections.Counter(p)cnt_s = collections.Counter()for i in range(m):cnt_s[s[i]] += 1if s[i] not in p:cnt_p[s[i]] = 0if i >= n:cnt_s[s[i - n]] -= 1if cnt_s == cnt_p:res.append(i - n + 1)return resif __name__ == '__main__':res = leetcode_fun2()print(res)  # [0, 6]

总结：

题目内容来源于leetcode链接：找到字符串中所有字母异位词