438. Find All Anagrams in a String

Medium
Given two strings s and p, return an array of all the start indices of p's anagrams in s. You may return the answer in any order.
An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.
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".
Constraints:
  • 1 <= s.length, p.length <= 3 * 104
  • s and p consist of lowercase English letters.

解題

func findAnagrams(s string, p string) []int {
l := len(p)
res := make([]int, 0)
m := make(map[byte]int)
​
for i:=0; i<l; i++ {
m[p[i]]++
}
​
sm := make(map[byte]int)
for i:=0; i<len(s); i++ {
sm[s[i]]++
​
flag := true
for k := range m {
if m[k] != sm[k] {
flag = false
}
}
​
if flag {
res = append(res, i - l + 1)
}
​
if i - l + 1 >= 0 {
sm[s[i - l + 1]]--
if sm[s[i - l + 1]] == 0{
delete(sm, s[i - l + 1])
}
}
}
​
return res
}
用陣列取代map會更快
func findAnagrams(s string, p string) []int {
if len(s) < len(p) {
return nil;
}
​
var result []int;
var pat, mem [26]int;
for i := range p {
pat[p[i]-'a']++;
mem[s[i]-'a']++;
}
​
for i := 0; i < len(s)-len(p)+1; i++ {
if pat == mem {
result = append(result, i);
}
if i+len(p) < len(s) {
mem[s[i]-'a']--;
mem[s[i+len(p)]-'a']++;
}
}
​
return result;
}