LeetCode: Find All Anagrams in a String

Posted on February 17, 2018July 26, 2020 by braindenny

Find All Anagrams in a String

Similar Problems:

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

Github: code.dennyzhang.com

Credits To: leetcode.com

Leave me comments, if you have better ways to solve.

// https://code.dennyzhang.com/find-all-anagrams-in-a-string
// Basic Ideas: sliding windows with fixed size
//  https://code.dennyzhang.com/find-all-anagrams-in-a-string
// Complexity: Time O(n), Space O(1)
func findAnagrams(s string, p string) []int {
    chars1 := make([]int, 26)
    chars2 := make([]int, 26)
    for i, _ := range p {
        index := int(p[i]-'a')
        chars2[index]++
    }
    res := []int{}
    // s[...i]
    for i:=0; i<len(s); i++ {
        // move the right
        index := int(s[i]-'a')
        chars1[index]++

        // move the left
        if i>=len(p) {
            index2 := int(s[i-len(p)]-'a')
            chars1[index2]--
        }

        // get a candidate
        j:=0
        for ; j<26; j++ {
            if chars1[j] != chars2[j] {
                break
            }
        }
        if j == 26 {
            res = append(res, i-len(p)+1)
        }
    }
    return res
}

Post Views: 2