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))
热门跟贴