NOTES · 学习笔记
找到字符串中所有字母异位词:固定窗口,逐格滑动
题目
这道题我们可以用滑动窗口来解决。先分析思路,我们看示例一:输入 s = "cbaebabacd",p = "abc",输出 [0,6]。
我们要从 s 这个字符串中找到所有 p 的字母异位词子串,p 是我们的目标,最后输出它们的起始下标。
那么我们首先定义一个窗口,窗口的大小就规定为 p 的长度。比如示例一中 p 的长度为 3,那么我们的窗口大小就是 3。
定义好窗口后,我们就要解决如何判断窗口中的字符是不是 p 的字母异位词,那么我们需要两个指针,一个左指针指向初始第一个元素,第二个右指针指向当前窗口中最后一个元素。
例如,s = "cbaebabacd",p = "abc",窗口大小为 3:left = 0,指向 c;right = 2,指向 a。当前窗口就是 "cba"。
那么,我们如何判断当前窗口是不是字母异位词呢?我们可以定义两个长度为 26 的数组,分别用来统计 p 和当前窗口中每个字母出现的次数。
因为题目中只有小写英文字母,所以可以用数组的下标对应字母,比如 a 对应 0,b 对应 1,以此类推。
统计完成后,我们只需要比较两个数组是否相等。一个数组统计 p,一个数组统计 s 的当前窗口。如果相等,说明两个字符串中的字母及其出现次数都相同,那么当前窗口就是一个字母异位词。
当前窗口是 "cba",它和 p = "abc" 中的字母及出现次数相同,所以这是一个字母异位词。我们定义一个 res 数组,用来保存异位词的起始下标,也就是 0。
接下来,我们开始移动窗口。首先移除左指针指向的元素 c,然后左指针向右移动一格。接着右指针也向右移动一格,并将新进入窗口的元素加入窗口。
每次移动后,我们都要判断当前窗口是不是字母异位词。如果是,就将当前左指针的下标保存到 res 数组中。一直重复这个过程,直到遍历完整个字符串。
func findAnagrams(s string, p string) []int {
left := 0 // 定义左指针
right := len(p) - 1 // 定义右指针
var pCount [26]int // 统计 p 中每个字母出现的次数
var window [26]int // 统计当前窗口中每个字母出现的次数
if len(p) > len(s) {
return nil // 目标字符串比 s 长,不可能找到符合条件的子串
}
for i := 0; i < len(p); i++ {
pCount[p[i]-'a']++ // 统计 p 中每个字母出现的次数
}
for i := 0; i < len(p); i++ {
window[s[i]-'a']++ // 统计初始窗口中每个字母出现的次数
}
res := []int{} // 保存字母异位词的起始下标
if window == pCount {
res = append(res, left) // 初始窗口符合条件时,保存左下标
}
for right < len(s)-1 {
window[s[left]-'a']-- // 移除窗口最左边的字母
left++ // 左指针向右移动一格
right++ // 右指针向右移动一格
window[s[right]-'a']++ // 把新进入窗口的字母计入统计
if window == pCount {
res = append(res, left) // 当前窗口符合条件时,保存左下标
}
}
return res
}