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 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))