龙空技术网

2024-05-11:用go语言,给定一个从零开始索引的字符串 s, 以及两

福大大架构师每日一题 74

前言:

目前兄弟们对“python获取字符串s长度的方法”可能比较关心,我们都需要了解一些“python获取字符串s长度的方法”的相关资讯。那么小编在网络上汇集了一些关于“python获取字符串s长度的方法””的相关资讯,希望看官们能喜欢,兄弟们一起来了解一下吧!

2024-05-11:用go语言,给定一个从零开始索引的字符串 s,

以及两个字符串 a 和 b,还有一个整数 k。

定义美丽下标为满足特定条件的字符串下标。

需要找到所有美丽下标,按升序排列后返回为数组形式。

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

输出:[16,33]。

答案2024-05-11:

chatgpt

题目来自leetcode3006。

大体步骤如下:

1.定义一个函数beautifulIndices,接受参数为字符串s,字符串a,字符串b和整数k,并返回一个整数数组ans

2.在函数beautifulIndices中,首先调用函数kmp找到字符串s中满足字符串a的子串的下标位置,将结果保存在变量posA中。

3.接下来,利用函数kmp找到字符串s中满足字符串b的子串的下标位置,将结果保存在变量posB中。

4.初始化变量jm,分别表示在posB中进行遍历的指针和posB的长度。

5.遍历posA中的每个下标i,在内部循环中,检查posB中从j开始的元素是否小于i-k。如果满足条件,则将j自增。

6.如果j仍然小于m,并且满足posB[j] - i的绝对值小于等于k,则将i添加到结果数组ans中。

7.最后,将结果数组ans返回。

总的时间复杂度为O(n),其中n是字符串s的长度。这是因为在KMP算法中,构建前缀表和匹配过程都需要线性时间。

总的空间复杂度为O(m),其中m是字符串b的长度。这是因为在KMP算法中需要使用一个长度为m的前缀表来存储匹配的信息。

Go完整代码如下:

package mainimport "fmt"func main() {    s := "isawsquirrelnearmysquirrelhouseohmy"    a := "my"    b := "squirrel"    k := 15    ans := beautifulIndices(s, a, b, k)    fmt.Println(ans)}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 && abs(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 abs(x int) int {    if x < 0 {        return -x    }    return x}

在这里插入图片描述

Python完整代码如下:

# -*-coding:utf-8-*-def main():    s = "isawsquirrelnearmysquirrelhouseohmy"    a = "my"    b = "squirrel"    k = 15        ans = beautiful_indices(s, a, b, k)    print(ans)def beautiful_indices(s, a, b, k):    posA = kmp(s, a)    posB = kmp(s, b)    j, m = 0, len(posB)    ans = []    for i in posA:        while j < m and posB[j] < i - k:            j += 1        if j < m and abs(posB[j] - i) <= k:            ans.append(i)        return ansdef 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        cnt = 0    pos = []    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 posdef abs(x):    if x < 0:        return -x    return xmain()

在这里插入图片描述

标签: #python获取字符串s长度的方法