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

1. 题目描述

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

2. 思路

• 暴力
• 滑动窗口+统计

3. 实现

3.1. 暴力

import "sort"

func findAnagrams(s string, p string) []int {
	if len(s) < len(p) {
		return nil
	}

	pRunes := []rune(p)
	sort.Slice(pRunes, func(i, j int) bool {
		return pRunes[i] < pRunes[j]
	})
	p = string(pRunes)

	res := make([]int, 0)
	sRunes := []rune(s)
	for i := 0; i < len(sRunes)-len(pRunes)+1; i++ {
		dst := make([]rune, len(pRunes))
		copy(dst, sRunes[i:i+len(pRunes)])
		sort.Slice(dst, func(i, j int) bool {
			return dst[i] < dst[j]
		})
		if string(dst) == p {
			res = append(res, i)
		}
	}
	return res
}

3.2. 滑动窗口+统计

func findAnagrams2(s string, p string) []int {
	if len(s) < len(p) {
		return nil
	}

	//统计字母出现的次数
	pCnt := make([]int, 26)
	sCnt := make([]int, 26)
	for i := 0; i < len(p); i++ {
		pCnt[p[i]-'a']++
		sCnt[s[i]-'a']++
	}

	//第一个位置是否相等
	res := make([]int, 0)
	if reflect.DeepEqual(sCnt, pCnt) {
		res = append(res, 0)
	}

	//剩下的位置是否相等
	for i := len(p); i < len(s); i++ {
		sCnt[s[i-len(p)]-'a']--
		sCnt[s[i]-'a']++
		if reflect.DeepEqual(sCnt, pCnt) {
			res = append(res, i-len(p)+1)
		}
	}

	return res

}

4. 参考

• 438. 找到字符串中所有字母异位词 - 力扣（LeetCode）