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

Problem: 438. 找到字符串中所有字母异位词

思路

基本思路是滑动窗口，维护一个长度为len(p)的窗口，同时用一个长度为26的数组用于记录p以及窗口中每个字符的数量。

滑动窗口移动时，把最左侧的字符移出窗口（计数-1），同时在右侧把一个新的字符加入窗口（计数+1），每次移动完成后，判断计数是否相等，相等则找到了异位词。

Code

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

	var res []int
	var pCount [26]int
	var sCount [26]int
	for i, ch := range p {
		pCount[ch-'a']++
		sCount[s[i]-'a']++
	}

	if pCount == sCount {
		res = append(res, 0)
	}

	for i, ch := range s[:len(s)-len(p)] {
		sCount[ch-'a']--
		sCount[s[i+len(p)]-'a']++

		if sCount == pCount {
			res = append(res, i+1)
		}
	}

	return res
}