写点什么

2024-08-03:用 go 语言,给定一个从 0 开始的字符串数组 `words`, 我们定义一个名为 `isPrefixAndSuffix` 的布尔函数,该函数接受两个字符串参数 `str1` 和

  • 2024-08-03
    北京
  • 本文字数:1686 字

    阅读完需:约 6 分钟

2024-08-03:用 go 语言,给定一个从 0 开始的字符串数组 words


我们定义一个名为 isPrefixAndSuffix 的布尔函数,该函数接受两个字符串参数 str1str2


str1 同时是 str2 的前缀和后缀时,函数返回 true;否则返回 false


例如,isPrefixAndSuffix("aba", "ababa") 返回 true


因为 "aba" 既是 "ababa" 的前缀也是后缀,而 isPrefixAndSuffix("abc", "abcd") 返回 false


我们的目标是以整数形式返回符合条件的下标对 (i, j) 的数量,


其中满足 i < jisPrefixAndSuffix(words[i], words[j])true


输入:words = ["a","aba","ababa","aa"]。


输出:4。


解释:在本示例中,计数的下标对包括:


i = 0 且 j = 1 ,因为 isPrefixAndSuffix("a", "aba") 为 true 。


i = 0 且 j = 2 ,因为 isPrefixAndSuffix("a", "ababa") 为 true 。


i = 0 且 j = 3 ,因为 isPrefixAndSuffix("a", "aa") 为 true 。


i = 1 且 j = 2 ,因为 isPrefixAndSuffix("aba", "ababa") 为 true 。


因此,答案是 4 。


答案 2024-08-03:


chatgpt


题目来自 leetcode3045。

大体步骤如下:

1 定义函数 isPrefixAndSuffix(str1, str2):实现一个函数,判断 str1 是否是 str2 的前缀和后缀。


  • 检查 str1 的长度是否大于 str2 的长度。如果是,直接返回 false

  • 确定 str2 的前缀是否与 str1 相同。

  • 确定 str2 的后缀是否与 str1 相同。

  • 如果上述两个条件都满足,返回 true;否则返回 false


2.遍历字符串数组 words


  • 使用两个嵌套循环,外层循环设定为 i,从 0 遍历到 len(words)-1,内层循环设定为 j,从 i+1 遍历到 len(words)-1。这样可以确保 i < j


3.调用 isPrefixAndSuffix 函数:在每对 (i, j) 中,调用 isPrefixAndSuffix(words[i], words[j])


  • 如果函数返回 true,则计数器增加 1。


4.返回计数器的值:最终,返回计数器的值,即为符合条件的下标对数量。

总时间复杂度

  • 外层循环走 n 次,内层循环从 i+1n,最坏情况下为 O(n)

  • 对于每一对 (i, j),调用 isPrefixAndSuffix 需要在 O(m) 时间内进行字符串的比较,其中 m 是前缀或后缀的长度。

  • 因此,总的时间复杂度为 O(n^2 * m),其中 m 是字符串的最长长度。

总额外空间复杂度

  • 本算法使用少量的额外空间来存储计数器和函数的一些局部变量,因此额外空间复杂度为 O(1)

  • 函数内部的字符串比较不需要额外的存储,仅使用常量空间来存储临时变量,主存储体在输入 words 中。


综上所述,时间复杂度为 O(n^2 * m),额外空间复杂度为 O(1)

Go 完整代码如下:

在package main
import ( "fmt")
func countPrefixSuffixPairs(words []string) (ans int64) { type pair struct{ x, y byte } type node struct { son map[pair]*node cnt int } root := &node{son: map[pair]*node{}} for _, s := range words { cur := root for i := range s { p := pair{s[i], s[len(s)-1-i]} if cur.son[p] == nil { cur.son[p] = &node{son: map[pair]*node{}} } cur = cur.son[p] ans += int64(cur.cnt) } cur.cnt++ } return}

func main() { words:=[]string{"a","aba","ababa","aa"} fmt.Println(countPrefixSuffixPairs(words))}
复制代码


Python 完整代码如下:

# -*-coding:utf-8-*-
class TrieNode: def __init__(self): self.children = {} self.count = 0
def count_prefix_suffix_pairs(words): root = TrieNode() ans = 0
for s in words: current = root length = len(s) for i in range(length): p = (s[i], s[length - 1 - i]) # 使用元组表示前缀和后缀字符对 if p not in current.children: current.children[p] = TrieNode() current = current.children[p] ans += current.count # 统计满足条件的对数 current.count += 1 # 更新当前节点的计数
return ans
if __name__ == "__main__": words = ["a", "aba", "ababa", "aa"] print(count_prefix_suffix_pairs(words))
复制代码



发布于: 刚刚阅读数: 2
用户头像

公众号:福大大架构师每日一题 2021-02-15 加入

公众号:福大大架构师每日一题

评论

发布
暂无评论
2024-08-03:用go语言,给定一个从 0 开始的字符串数组 `words`, 我们定义一个名为 `isPrefixAndSuffix` 的布尔函数,该函数接受两个字符串参数 `str1` 和_福大大架构师每日一题_福大大架构师每日一题_InfoQ写作社区