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

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

words

我们定义一个名为的布尔函数，该函数接受两个字符串参数和。

isPrefixAndSuffix

str1

str2

当同时是的前缀和后缀时，函数返回；否则返回。

str1

str2

true

false

例如，返回，

isPrefixAndSuffix("aba", "ababa")

true

因为 "aba" 既是 "ababa" 的前缀也是后缀，而返回。

isPrefixAndSuffix("abc", "abcd")

false

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

其中满足且为。

i < j

isPrefixAndSuffix(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

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

3.调用函数：在每对中，调用。

isPrefixAndSuffix

(i, j)

isPrefixAndSuffix(words[i], words[j])

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

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

总时间复杂度

• •外层循环走次，内层循环从到，最坏情况下为。
• n
• i+1
• n
• O(n)
• •对于每一对，调用需要在时间内进行字符串的比较，其中是前缀或后缀的长度。
• (i, j)
• isPrefixAndSuffix
• O(m)
• m
• •因此，总的时间复杂度为，其中是字符串的最长长度。
• O(n^2 * m)
• m

总额外空间复杂度

• •本算法使用少量的额外空间来存储计数器和函数的一些局部变量，因此额外空间复杂度为。
• O(1)
• •函数内部的字符串比较不需要额外的存储，仅使用常量空间来存储临时变量，主存储体在输入中。
• words

综上所述，时间复杂度为，额外空间复杂度为。

O(n^2 * m)

O(1)

Go完整代码如下：

在packagemain
import(
"fmt"
)
funccountPrefixSuffixPairs(words[]string)(ansint64){
typepairstruct{x,ybyte}
typenodestruct{
sonmap[pair]*node
cntint
}
root:=&node{son:map[pair]*node{}}
for_,s:=rangewords{
cur:=root
fori:=ranges{
p:=pair{s[i],s[len(s)-1-i]}
ifcur.son[p]==nil{
cur.son[p]=&node{son:map[pair]*node{}}
}
cur=cur.son[p]
ans+=int64(cur.cnt)
}
cur.cnt++
}
return
}
funcmain(){
words:=[]string{"a","aba","ababa","aa"}
fmt.Println(countPrefixSuffixPairs(words))
}

Python完整代码如下：

#-*-coding:utf-8-*-
classTrieNode:
def__init__(self):
self.children={}
self.count=0
defcount_prefix_suffix_pairs(words):
root=TrieNode()
ans=0
forsinwords:
current=root
length=len(s)
foriinrange(length):
p=(s[i],s[length-1-i])#使用元组表示前缀和后缀字符对
ifpnotincurrent.children:
current.children[p]=TrieNode()
current=current.children[p]
ans+=current.count#统计满足条件的对数
current.count+=1#更新当前节点的计数
returnans
if__name__=="__main__":
words=["a","aba","ababa","aa"]
print(count_prefix_suffix_pairs(words))