Find All Anagrams In A String

题目描述

找到字符串中所有字母异位词

给定一个字符串s和一个非空字符串p，找到s中所有是p的字母异位词的子串，返回这些子串的起始索引。

假定字符串只包含小写英文字母。

示例

输入:
s: "cbaebabacd" p: "abc"

输出:
[0, 6]

解释:
起始索引等于 0 的子串是 "cba", 它是 "abc" 的字母异位词。
起始索引等于 6 的子串是 "bac", 它是 "abc" 的字母异位词。

解法

解法一：暴力循环

• 时间复杂度：o(slength * plength)

• 空间复杂度：O(m)，m表示字符集的大小。

func findAnagrams(s string, p string) []int {
    ans := []int{}
    for i := 0; i < len(s)-len(p)+1; i++ {
        tmp := make([]int, 26)
        for j := 0; j < len(p); j++ {
            tmp[p[j]-'a']++
        }
        ok := true
        for j := i; j < i+len(p); j++ {
            ch := s[j] - 'a'
            tmp[ch]--
            if tmp[ch] < 0 {
                ok = false
            }
        }
        if ok {
            ans = append(ans, i)
        }
    }
    return ans
}

解法二：滑动窗口

• 时间复杂度：O(n)

• 空间复杂度：O(m)，m表示字符集的大小

func findAnagrams(s string, p string) []int {
    ans := []int{}
    left, right := 0, 0
    pcnt := make([]int, 26)
    for i := 0; i < len(p); i++ {
        pcnt[p[i]-'a']++
    }
    scnt := make([]int, 26)
    for right < len(s) {
        ch := s[right] - 'a'
        scnt[ch]++
        if scnt[ch] > pcnt[ch] {
            for i := left; i <= right; i++ {
                scnt[s[i]-'a']--
                if s[i] == s[right] {
                    left = i + 1
                    break
                }
            }
        }
        right++

        if right-left == len(p) {
            ans = append(ans, left)
        }
    }
    return ans
}