0438. Find All Anagrams in a String

# 438. Find All Anagrams in a String#

## 题目 #

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".

``````

## 代码 #

``````
package leetcode

func findAnagrams(s string, p string) []int {
var freq [256]int
result := []int{}
if len(s) == 0 || len(s) < len(p) {
return result
}
for i := 0; i < len(p); i++ {
freq[p[i]-'a']++
}
left, right, count := 0, 0, len(p)

for right < len(s) {
if freq[s[right]-'a'] >= 1 {
count--
}
freq[s[right]-'a']--
right++
if count == 0 {
result = append(result, left)
}
if right-left == len(p) {
if freq[s[left]-'a'] >= 0 {
count++
}
freq[s[left]-'a']++
left++
}

}
return result
}

``````

Sep 6, 2020