2024-05-18:用go语言,给定一个从 0 开始的字符串 s,以及两个子字符串 a 和 b,还有一个整数 k

2024-05-18:用go语言,给定一个从 0 开始的字符串 s,以及两个子字符串 a 和 b,还有一个整数 k。

定义一个“美丽下标”,当满足以下条件时:

1.找到字符串 a 在字符串 s 中的位置,且该位置范围为 0 <= i <= s.length - a.length。

2.找到字符串 b 在字符串 s 中的位置,且该位置范围为 0 <= j <= s.length - b.length。

3.两个字符串的匹配位置之差的绝对值不超过 k。

需要按照美丽下标的大小升序排列,然后以数组的形式返回这些下标。

输入:s = “isawsquirrelnearmysquirrelhouseohmy”, a = “my”, b = “squirrel”, k = 15。

输出:[16,33]。

答案2024-05-18:

chatgpt

题目来自leetcode3008。

大体步骤如下:

1.定义了 main 函数,其中给定了字符串 s、子字符串 a 和 b,以及整数 k。

2.在 main 函数中调用 beautifulIndices 函数,并输出结果。

3.beautifulIndices 函数中调用了 kmp 函数来找到字符串 a 和 b 在字符串 s 中的所有可能位置。

4.在 kmp 函数中,首先构建了 pattern 的前缀函数 pi。

5.对于子串 a,通过 KMP 算法寻找所有匹配的位置,将它们存储在 posA 中。

6.对于子串 b,同样使用 KMP 算法来寻找所有匹配的位置,将它们存储在 posB 中。

7.然后遍历 posA 中的每个位置 i,在 posB 中查找满足条件的位置 j 和 k,更新 ans。

8.将找到的美丽下标按照升序排列,并以数组形式返回。

总的时间复杂度:

  • KMP 算法的时间复杂度为 O(n + m),其中 n 是字符串长度,m 是模式串长度。在该问题中,分别对两个子串执行 KMP 搜索,因此总的时间复杂度为 O(n + m) + O(n + m) = O(n + m)。

  • 遍历 posA 和 posB 的时间复杂度为 O(n) + O(n) = O(n),其中 n 是字符串长度。

总的额外空间复杂度:

  • 在 KMP 函数中,构建了模式串的前缀函数 pi,使用了额外的空间来存储 pi 数组,其大小等于模式串的长度,因此空间复杂度为 O(m)。

  • 在 beautifulIndices 函数中,存储了所有匹配的位置,即创建了 posA 和 posB 数组来存储这些位置,空间复杂度为 O(n)。

  • 因此,总的额外空间复杂度为 O(m) + O(n)。

综上所述,总的时间复杂度为 O(n + m),总的额外空间复杂度为 O(m) + O(n)。

Go完整代码如下:

package main

import "fmt"

func beautifulIndices(s, a, b string, k int) (ans []int) {
    posA := kmp(s, a)
    posB := kmp(s, b)

    j, m := 0, len(posB)
    for _, i := range posA {
        for j < m && posB[j] < i-k {
            j++
        }
        if j < m && posB[j] <= i+k {
            ans = append(ans, i)
        }
    }
    return
}

func kmp(text, pattern string) (pos []int) {
    m := len(pattern)
    pi := make([]int, m)
    cnt := 0
    for i := 1; i < m; i++ {
        v := pattern[i]
        for cnt > 0 && pattern[cnt] != v {
            cnt = pi[cnt-1]
        }
        if pattern[cnt] == v {
            cnt++
        }
        pi[i] = cnt
    }

    cnt = 0
    for i, v := range text {
        for cnt > 0 && pattern[cnt] != byte(v) {
            cnt = pi[cnt-1]
        }
        if pattern[cnt] == byte(v) {
            cnt++
        }
        if cnt == m {
            pos = append(pos, i-m+1)
            cnt = pi[cnt-1]
        }
    }
    return
}

func main() {
    s := "isawsquirrelnearmysquirrelhouseohmy"
    a := "my"
    b := "squirrel"
    k := 15

    result := beautifulIndices(s, a, b, k)
    fmt.Println("Result:", result)
}

在这里插入图片描述

Python完整代码如下:

# -*-coding:utf-8-*-

def beautiful_indices(s, a, b, k):
    def kmp(text, pattern):
        m = len(pattern)
        pi = [0] * m
        cnt = 0
        for i in range(1, m):
            v = pattern[i]
            while cnt > 0 and pattern[cnt] != v:
                cnt = pi[cnt - 1]
            if pattern[cnt] == v:
                cnt += 1
            pi[i] = cnt

        pos = []
        cnt = 0
        for i, v in enumerate(text):
            while cnt > 0 and pattern[cnt] != v:
                cnt = pi[cnt - 1]
            if pattern[cnt] == v:
                cnt += 1
            if cnt == m:
                pos.append(i - m + 1)
                cnt = pi[cnt - 1]
        return pos

    posA = kmp(s, a)
    posB = kmp(s, b)

    ans = []
    j, m = 0, len(posB)
    for i in posA:
        while j < m and posB[j] < i - k:
            j += 1
        if j < m and posB[j] <= i + k:
            ans.append(i)

    return ans

s = "isawsquirrelnearmysquirrelhouseohmy"
a = "my"
b = "squirrel"
k = 15

result = beautiful_indices(s, a, b, k)
print("Result:", result)

在这里插入图片描述

本作品采用《CC 协议》,转载必须注明作者和本文链接
微信公众号:福大大架构师每日一题。最新面试题,涉及golang,rust,mysql,redis,云原生,算法,分布式,网络,操作系统。
讨论数量: 0
(= ̄ω ̄=)··· 暂无内容!

讨论应以学习和精进为目的。请勿发布不友善或者负能量的内容,与人为善,比聪明更重要!
未填写
文章
482
粉丝
23
喜欢
37
收藏
22
排名:456
访问:2.0 万
私信
所有博文
社区赞助商