class Solution {
public:
long long countPrefixSuffixPairs(vector<string>& words) {
}
};
100208. 统计前后缀下标对 II
给你一个下标从 0 开始的字符串数组 words 。
定义一个 布尔 函数 isPrefixAndSuffix ，它接受两个字符串参数 str1 和 str2 ：
str1 同时是 str2 的前缀（prefix）和后缀（suffix）时，isPrefixAndSuffix(str1, str2) 返回 true，否则返回 false。例如，isPrefixAndSuffix("aba", "ababa") 返回 true，因为 "aba" 既是 "ababa" 的前缀，也是 "ababa" 的后缀，但是 isPrefixAndSuffix("abc", "abcd") 返回 false。
以整数形式，返回满足 i < j 且 isPrefixAndSuffix(words[i], words[j]) 为 true 的下标对 (i, j) 的 数量 。
示例 1：
输入：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 。
示例 2：
输入：words = ["pa","papa","ma","mama"]
输出：2
解释：在本示例中，计数的下标对包括：
i = 0 且 j = 1 ，因为 isPrefixAndSuffix("pa", "papa") 为 true 。
i = 2 且 j = 3 ，因为 isPrefixAndSuffix("ma", "mama") 为 true 。
因此，答案是 2 。
示例 3：
输入：words = ["abab","ab"]
输出：0
解释：在本示例中，唯一有效的下标对是 i = 0 且 j = 1 ，但是 isPrefixAndSuffix("abab", "ab") 为 false 。
因此，答案是 0 。
提示：
1 <= words.length <= 1051 <= words[i].length <= 105words[i] 仅由小写英文字母组成。words[i] 的长度之和不超过 5 * 105 。原站题解
golang 解法, 执行用时: 262 ms, 内存消耗: 164.7 MB, 提交时间: 2024-02-19 09:52:10
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
}
python3 解法, 执行用时: 1318 ms, 内存消耗: 182.1 MB, 提交时间: 2024-02-19 09:51:12
# 字典树， __slots__定义的属性仅对当前类示例起限制作用，对继承的子类是不起限制作用
class Node:
__slots__ = 'son', 'cnt'
def __init__(self):
self.son = dict()
self.cnt = 0
class Solution:
def countPrefixSuffixPairs(self, words: List[str]) -> int:
ans = 0
root = Node()
for s in words:
cur = root
for p in zip(s, reversed(s)):
if p not in cur.son:
cur.son[p] = Node()
cur = cur.son[p]
ans += cur.cnt
cur.cnt += 1
return ans