题目描述
给定两个字符串 s
和 p
,找到 s
中所有 p
的 异位词 的子串,返回这些子串的起始索引。不考虑答案输出的顺序。
异位词 指由相同字母重排列形成的字符串(包括相同的字符串)。
示例 1:
输入: s = “cbaebabacd”, p = “abc”
输出: [0,6]
解释:
起始索引等于 0 的子串是 “cba”, 它是 “abc” 的异位词。
起始索引等于 6 的子串是 “bac”, 它是 “abc” 的异位词。
示例 2:
输入: s = “abab”, p = “ab”
输出: [0,1,2]
解释:
起始索引等于 0 的子串是 “ab”, 它是 “ab” 的异位词。
起始索引等于 1 的子串是 “ba”, 它是 “ab” 的异位词。
起始索引等于 2 的子串是 “ab”, 它是 “ab” 的异位词。
提示:
1 <= s.length, p.length <= 3 * 104
s
和p
仅包含小写字母
代码及注释
func findAnagrams(s string, p string) []int {
// 初始化两个数组来存储字符出现的次数
pCh, sCh := [26]int{}, [26]int{}
// 存储结果的切片
res := make([]int, 0)
// 统计字符串p中每个字符的出现次数
for _, ch := range p {
pCh[ch - 'a']++
}
// 使用滑动窗口遍历字符串s
left, right := 0, 0
for right < len(s) {
// 更新sCh中当前字符的出现次数
sCh[s[right] - 'a']++
right++
// 当窗口大小等于p的长度时,进行判断
if right - left == len(p) {
// 如果两个数组相同,说明找到了一个异位词
if isSame(sCh, pCh) {
res = append(res, left)
}
// 移动左边界,并更新sCh中对应字符的出现次数
sCh[s[left] - 'a']--
left++
}
}
return res
}
// 判断两个数组是否相同
func isSame(sCh, pCh [26]int) bool {
for i := 0; i < 26; i++ {
if sCh[i] != pCh[i] {
return false
}
}
return true
}
代码解释:
初始化数组:
pCh, sCh := [26]int{}, [26]int{}
用两个长度为26的数组
pCh
和sCh
来分别记录字符串p
和当前滑动窗口中的字符出现的次数。初始化结果切片:
res := make([]int, 0)
用于存储找到的异位词的起始索引。
统计字符出现次数:
for _, ch := range p { pCh[ch - 'a']++ }
遍历字符串
p
,统计每个字符出现的次数。滑动窗口遍历字符串s:
left, right := 0, 0 for right < len(s) { // ... }
使用两个指针
left
和right
组成滑动窗口,遍历字符串s
。更新字符出现次数:
sCh[s[right] - 'a']++ right++
更新滑动窗口中当前字符
s[right]
的出现次数。判断是否找到异位词:
if right - left == len(p) { if isSame(sCh, pCh) { res = append(res, left) } sCh[s[left] - 'a']-- left++ }
当滑动窗口的大小等于
p
的长度时,判断当前窗口内的字符出现次数与p
的字符出现次数是否相同。如果相同,则将左指针left
添加到结果切片中,并移动左指针,并更新对应字符的出现次数。判断两个数组是否相同:
func isSame(sCh, pCh [26]int) bool { for i := 0; i < 26; i++ { if sCh[i] != pCh[i] { return false } } return true }
该函数用于判断两个数组
pCh
和sCh
是否相同,即判断当前窗口内的字符出现次数与p
的字符出现次数是否相同。