Leetcode - Find All Anagrams in a String

https://leetcode.com/problems/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".

func findAnagrams(s string, p string) []int {
    pHash := map[byte]int{}
    for i := 0; i < len(p); i++ {
        pHash[p[i]]++
    }
    result := []int{}
    i := 0
    sHash := map[byte]int{}
    count := 0
    for i < len(s) {
        if _, ok := pHash[s[i]]; !ok {
            if count > 0 {
                count--
            }
            i++
            continue
        }
        if i >= len(s) {
            break
        }

        for j := i + count; j < len(s) && count < len(p); j++ {
            sHash[s[j]]++
            count++
        }
        /*
        fmt.Println("i: ", i)
        fmt.Println("sHash: ", sHash)
        fmt.Println("pHash: ", pHash)
        */
        found := true
        for key, val := range pHash {
            if sVal, sOk := sHash[key]; !sOk || sVal != val {
                found = false
            }
        }
        if found {
            result = append(result, i)
        }
        sHash[s[i]]--
        count--
        if sHash[s[i]] <= 0 {
            delete(sHash, s[i])
        }
        i++
    }
    return result
}

• 相关文章
• 全局相关文章