Leetcode - Longest Substring with At Most K Distinct Characters
Leetcode - Permutation in String

Leetcode - Find All Anagrams in a String

violet posted @ May 18, 2020 01:19:49 AM in 算法 with tags Algorithm Golang SlidingWindow hash , 342 阅读

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
}
Rs.ap.gov.in 2023 说:
Nov 15, 2022 01:29:39 AM

Property ownership entails more than the owner’s name and basic recognition. The property should be registered and legal documents issued to the owner. This helps in property tax collection and an easy transfer process from seller to buyer. Rs.ap.gov.in 2023 To ensure all properties are registered, the Andhra Pradesh state government and legal bodies have developed various documents such as the Encumbrance certificate.


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter