LeetCode 438. Find All Anagrams in a String

Description

Given a string s and a non-empty string p, find all the start indices of p’s anagrams in s.

Strings consists of lowercase English letters only and the length of both strings s and p will not be larger than 20,100.

The order of output does not matter.

Example 1:

```Input:
s: "cbaebabacd" p: "abc"

Output:
[0, 6]

Explanation:
The substring with start index = 0 is "cba", which is an anagram of "abc".
The substring with start index = 6 is "bac", which is an anagram of "abc".
```

Example 2:

```Input:
s: "abab" p: "ab"

Output:
[0, 1, 2]

Explanation:
The substring with start index = 0 is "ab", which is an anagram of "ab".
The substring with start index = 1 is "ba", which is an anagram of "ab".
The substring with start index = 2 is "ab", which is an anagram of "ab".
```

思路

• 第一种思路比较简单直接，我们用 p 字符串中的字符构造一个字典，键为字符，值为每个字符在 p 中出现的次数，记这个字典为 p_dict;
• 我们用 s 字符串的前 len(p) 个字符构建一个字典，同样的，键为字符，值为每个字符在 s[0:len(p)] 中出现的次数,记这个字典为 tmp_dict；
• 我们比较这两个字典是否相等，若相等，说明 s[0:len(p)] 满足题意，在结果数组中记下 0 的位置；
• 我们更新 tmp_dict，通过减少 tmp_dict 中 s[i] 元素，增加 s[i+len(p)] 的方式更新 ；
• 继续比较 tmp_dict 和 p_dict 是否相等；
```# -*- coding: utf-8 -*-
# @Author:             何睿
# @Create Date:        2020-05-05 15:29:17

from typing import List
from copy import deepcopy
from collections import defaultdict

class Solution:
def findAnagrams(self, s: str, p: str) -> List[int]:

if not s or not p:
return []

p_dict = defaultdict(int)
tmp_dict = defaultdict(int)
for char in p:
p_dict[char] += 1

for char in s[:len(p)]:
tmp_dict[char] += 1

res = []

for i in range(0, len(s) - len(p)):
if tmp_dict == p_dict:
res.append(i)

tmp_dict[s[i]] -= 1
if tmp_dict[s[i]] == 0:
tmp_dict.pop(s[i])
tmp_dict[s[i + len(p)]] += 1

if tmp_dict == p_dict:
res.append(len(s) - len(p))
return res

```
• 还有另外一种方式，记录 p 中所有字符的 cnt，遍历 s 中的字符，不断的减小 cnt 的值，当 cnt 的值为 0 时，说明找到了一个满足题意的解；
• 同样的，我们用字符串 p 中的字符构造一个字典，键为字符，值为每个字符在 p 中出现的次数，记这个字典为 p_dict，键为 key，值为 value;这个字典的含义为：要形成字符串 p 的 Anagram，还需要字符 key 各 value 个；
• 如 p = “aavc”，则 p_dict = {“a”:2,”v”:1,”c”:1}，表示需要形成字符串 “aavc” 的 Anagram ，还需要 a 字符 2 个，v 字符 1 个，c 字符 1个；
• 我们用两个指针 left，right，从左向右遍历；
• 记字符 s[right] 为 t，让 p_dict[t] -1，表示「要形成字符 p，对字符 t 的需要减少 1」；此时检查 p_dict[t] 是否大于 0，若大于零，则 cnt -1；
• 检查 cnt 是否等于 0，若为零，表示 s 中 left 到 right 的字符，可以形成 p；
• 当 right – left 包含的字符个数等于 p 时,需要将 left 向右边移动；
• 此时 p_dict[s[left]] 自增 1，如果 p_dict[s[left]] 大于等于零，则 cnt + 1；
• 如果 p_dict[s[left]] 小于 0，说明在字符 p 中没有字符 s[left]
```from typing import List
from copy import deepcopy
from collections import defaultdict

class Solution:

def findAnagrams(self, s: str, p: str) -> List[int]:

if not s or not p:
return []

p_dict = defaultdict(int)
for char in p:
p_dict[char] += 1

left, right, cnt = 0, 0, len(p)
res = []

while right < len(s):
p_dict[s[right]] -= 1

if p_dict[s[right]] >= 0:
cnt -= 1
if cnt == 0:
res.append(left)
if right - left + 1 == len(p):
if p_dict[s[left]] >= 0: # 大于零，说明 p 中有字符 s[left]，否则 p 中没有 s[left]
cnt += 1
p_dict[s[left]] += 1
left += 1

right += 1

return res

```