2021-12-18：找到字符串中所有字母异位词。 给定两个字符
原创2021-12-18：找到字符串中所有字母异位词。 给定两个字符
原创
福大大架构师每日一题
发布于 2021-12-18 22:15:21
发布于 2021-12-18 22:15:21
2021-12-18：找到字符串中所有字母异位词。
给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。
异位词 指由相同字母重排列形成的字符串（包括相同的字符串）。
力扣438。
答案2021-12-18：
滑动窗口。欠账表。
时间复杂度：O(N)。
空间复杂度：O(1)。
代码用golang编写。代码如下：
package main
import "fmt"
func main() {
s := "abab"
p := "ab"
ret := findAnagrams(s, p)
fmt.Println(ret)
}
func findAnagrams(s, p string) []int {
ans := make([]int, 0)
if len(s) < len(p) {
return ans
}
str := []byte(s)
N := len(str)
pst := []byte(p)
M := len(pst)
map0 := make(map[byte]int)
for _, cha := range pst {
map0[cha]++
}
all := M
for end := 0; end < M-1; end++ {
if _, ok := map0[str[end]]; ok {
count := map0[str[end]]
if count > 0 {
all--
}
map0[str[end]] = count - 1
}
}
for end, start := M-1, 0; end < N; end, start = end+1, start+1 {
if _, ok := map0[str[end]]; ok {
count := map0[str[end]]
if count > 0 {
all--
}
map0[str[end]] = count - 1
}
if all == 0 {
ans = append(ans, start)
}
if _, ok := map0[str[start]]; ok {
count := map0[str[start]]
if count >= 0 {
all++
}
map0[str[start]] = count + 1
}
}
return ans
}执行结果如下：
图片
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
评论
登录后参与评论
推荐阅读