一、题目
给定两个字符串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" 的异位词。
二、解答实现
相当于是用字符串p与匹配字符串s，与上一道滑动窗口题目不一样的是，这个窗口大小明显是固定的，就是p的长度。拿大小是p长度的滑动窗口去一个个找。但是如果我们每遍历一个窗口，就要把小窗口中所有元素再遍历完一遍去对照哈希表，这样复杂度也是很高的。在python中我们可以借助排序这个api，对照两个字符串是否相等就可以。具体代码如下：
from typing import List class Solution: def findAnagrams(self, s: str, p: str) -> List[int]: sorted_p = sorted(p) # 直接将p排序 left, right = 0, len(p) - 1 # 窗口左右边界，固定大小。同时移动 ans = [] while right < len(s): if sorted(s[left, right + 1]) == sorted_p: # 找到了异位词 ans.append(left) # 添加左边界 left += 1 right += 1 else: left += 1 right += 1 return ans
