给定一个字符串 s 和一个非空字符串 p，找到 s 中所有是 p 的字母异位词的子串，返回这些子串的起始索引。
字符串只包含小写英文字母，并且字符串 s 和 p 的长度都不超过 20100。
说明：
字母异位词指字母相同，但排列不同的字符串。
不考虑答案输出的顺序。
示例 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" 的字母异位词。
针对问题 1 很容易，因为是长度固定为 p 的滑动窗口，而针对如何存储 p 串这个问题，我们可以考虑用桶来装，这个桶既可以用 26 个元素的数组（作用其实也是哈希表）也可以用哈希表
public List<Integer> findAnagrams(String s, String p) {
List<Integer> res = new LinkedList<>();
if (s == null || p == null || s.length() < p.length())
return res;
int[] ch = new int[26];
//统计p串字符个数
for (char c : p.toCharArray())
ch[c - 'a']++;
//把窗口扩成p串的长度
int start = 0, end = 0, rest = p.length();
for (; end < p.length(); end++) {
char temp = s.charAt(end);
ch[temp - 'a']--;
if (ch[temp - 'a'] >= 0)
rest--;
}
if (rest == 0)
res.add(0);
//开始一步一步向右移动窗口。
while (end < s.length()) {
//左边的拿出来一个并更新状态
char temp = s.charAt(start);
if (ch[temp - 'a'] >= 0)
rest++;
ch[temp - 'a']++;
start++;
//右边的拿进来一个并更新状态
temp = s.charAt(end);
ch[temp - 'a']--;
if (ch[temp - 'a'] >= 0)
rest--;
end++;
// 状态合法就存到结果集合
if (rest == 0)
res.add(start);
}
return res;
}
Python 解法具体做法稍有一点不同，没有使用 rest 变量，而是直接取的哈希表的长度。其中 哈希表的 key 是字符，value 是窗口内字符出现次数。这样当 value 为 0 时，我们移除 key，这样当哈希表容量为 0，说明我们找到了一个异位词。
class Solution:
def findAnagrams(self, s: str, p: str) -> List[int]:
target = collections.Counter(p)
ans = []
for i in range(len(s)):
if i >= len(p):
target[s[i - len(p)]] += 1
if target[s[i - len(p)]] == 0:
del target[s[i - len(p)]]
target[s[i]] -= 1
if target[s[i]] == 0:
del target[s[i]]
if len(target) == 0:
ans.append(i - len(p) + 1)
return ans
class FrequencyDict:
def __init__(self, s):
self.d = collections.Counter()
for char in s:
self.increment(char)
def _del_if_zero(self, char):
if self.d[char] == 0:
del self.d[char]
def is_empty(self):
return not self.d
def decrement(self, char):
self.d[char] -= 1
self._del_if_zero(char)
def increment(self, char):
self.d[char] += 1
self._del_if_zero(char)
class Solution:
def findAnagrams(self, s: str, p: str) -> List[int]:
ans = []
freq = FrequencyDict(p)
for char in s[:len(p)]:
freq.decrement(char)
if freq.is_empty():
ans.append(0)
for i in range(len(p), len(s)):
start, end = s[i - len(p)], s[i]
freq.increment(start)
freq.decrement(end)
if freq.is_empty():
ans.append(i - len(p) + 1)
return ans
