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完整代码如下：

在package mainimport ("fmt")func countPrefixSuffixPairs(words []string) (ans int64) {type pair struct{ x, y byte }type node struct {son map[pair]*nodecnt int}root := &node{son: map[pair]*node{}}for _, s := range words {cur := rootfor 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 = 0def 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 ansif __name__ =="__main__": words = ["a","aba","ababa","aa"] print(count_prefix_suffix_pairs(words))