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**：
- • 使用两个嵌套循环，外层循环设定为
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 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完整代码如下：
代码语言：javascript复制在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完整代码如下：
代码语言：javascript复制# -*-coding:utf-8-*-
classTrieNode:
def__init__(self):
self.children ={}
self.count =0
defcount_prefix_suffix_pairs(words):
root =TrieNode()
ans =0
for s in words:
current = root
length =len(s)
for i inrange(length):
p =(s[i], s[length -1- i])# 使用元组表示前缀和后缀字符对
if p notin 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))
