leecode题解Golang版本：LCR 015. 找到字符串中所有字母异位词

前言

笔者在该专栏会展示golang的题解，该题解已经经过leecode的用例验证，期望能够给大家一些启发。

题目描述

leecode连接
给定两个字符串 s 和 p，找到 s 中所有 p 的 变位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。

变位词 指字母相同，但排列不同的字符串。

题解

func findAnagrams(s string, p string) []int {
	m, valid := counter(p)
	res := make([]int, 0)
	for l, r := 0, 0; r < len(s); r++ {
		if v, ok := m[s[r]]; ok {
			m[s[r]]--
			if v == 1 {
				valid--
			}
		}
		for r-l > len(p)-1 {
			if v, ok := m[s[l]]; ok {
				m[s[l]]++
				if v == 0 {
					valid++
				}
			}
			l++
		}
		if valid == 0 {
			res = append(res, l)
		}

	}
	return res
}
func counter(p string) (map[uint8]int, int) {
	res := make(map[uint8]int)
	for i := 0; i < len(p); i++ {
		res[p[i]]++
	}
	return res, len(res)
}

核心细节一：巧用map和valid常量判断字符是否互为全排列

leecode-LCR 017. 最小覆盖子串（golang版本
笔者在该文章中阐述了该思路

核心细节二：滑动窗口的收缩时机

以s=abab，t=ab为例，我们来展示该滑动窗口的伸展和收缩逻辑。

此刻我们可以看出滑动窗口内包含的字符串是ab,恰好与ab相同，我们记录一下当前滑动窗口左边界的刻度0，该值是我们需要的。此时滑动窗口的大小恰好为t的长度，现在我们就可以继续维持滑动窗口的大小，右边界拓展一个位置，左边界收缩一个位置，然后统计新的滑动窗口内的字符串是否符合需求。当右边界到达s字符串末端，此时整个s字符串中的所有与t相同长度的子字符串都已经遍历完毕了。