【Leetcode】438. 找到字符串中所有字母异位词
题目链接
【Leetcode】438. 找到字符串中所有字母异位词
代码
func findAnagrams(s string, p string) []int {
// 枚举p串,统计p串字符出现的次数
cnt := map[byte]int{}
for idx := range p {
cnt[p[idx]]++
}
// 记录p串中总共有多少种字符
total := len(cnt)
// s串和p串的字符串长度
lenS, lenP := len(s), len(p)
i, j := 0, 0
// 统计满足刚好相等的字符的种类数
ans := []int{}
// 统计当前窗口内符合字符串种类数跟个数都符合的字符种数
time := 0
// 枚举s串
for j < lenS {
// 新字符s[j]放入窗口中,cnt中该字符的个数-1
cnt[s[j]]--
// 如果新字符放入窗口之后,cnt中该字符的个数为-1,说明符合条件的字符种数要-1,新字符放入窗口之前,是符合条件的
if cnt[s[j]] == -1 {
time--
} else if cnt[s[j]] == 0 {
// 如果新字符放入窗口之后,cnt中该字符的个数为0,说明符合条件的字符种类数要+1,新字符放入窗口之后,刚好符合条件
time++
}
// 如果窗口中的字符串长度 > p串长度,则
if j-i+1 > lenP {
// 把窗口左边界的字符移出窗口
cnt[s[i]]++
// 如果左边界字符移出窗口之后, cnt中该字符的个数为0,说明这个字符移出窗口之后,是符合条件的
if cnt[s[i]] == 0 {
time++
} else if cnt[s[i]] == 1 {
// 如果左边界字符移出窗口之后,cnt中该字符的个数为1,说明该字符移出窗口之前,是刚好符合条件的
time--
}
i++// 窗口左边界右移
}
j++// 窗口右边界右移动
// 如果此时窗口内的字符串刚好符合条件,则把左边界的下标放入结果数组
if time == total {
ans = append(ans, i)
}
}
return ans
}