找到字符串中所有字母异位词。 给定两个字符串 s 和 p,找到 s 中所有 p 的 异位词 的子串,返回这些子串的起始索引。不考虑答案输出的顺序。
  xaeiTka4h8LY 29天前 37 0

找到字符串中所有字母异位词。
给定两个字符串 s 和 p,找到 s 中所有 p 的 异位词 的子串,返回这些子串的起始索引。不考虑答案输出的顺序。
异位词 指由相同字母重排列形成的字符串(包括相同的字符串)。

滑动窗口。欠账表。
时间复杂度: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
}

执行结果如下:

2021-12-18:找到字符串中所有字母异位词。 给定两个字符串 s 和 p,找到 s 中所有 p 的 异位词 的子串,返回这些子串的起始索引。不考虑答案输出的顺序。 异位词 指由相同字母重排列形成

【版权声明】本文内容来自摩杜云社区用户原创、第三方投稿、转载,内容版权归原作者所有。本网站的目的在于传递更多信息,不拥有版权,亦不承担相应法律责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@moduyun.com

  1. 分享:
最后一次编辑于 29天前 0

暂无评论

推荐阅读
xaeiTka4h8LY