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;
}