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

2023-12-19 07:22:01

前言

笔者在该专栏会展示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为例,我们来展示该滑动窗口的伸展和收缩逻辑。

区间范围是否包含字符串t滑动窗口大小是否与t相等
[0,0)
[0,1)
[0,2)

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

文章来源:https://blog.csdn.net/weixin_38757398/article/details/135036230
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。