class Solution {
public:
int countPrefixSuffixPairs(vector<string>& words) {
}
};
100212. 统计前后缀下标对 I
给你一个下标从 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 <= 501 <= words[i].length <= 10words[i] 仅由小写英文字母组成。原站题解
python3 解法, 执行用时: 40 ms, 内存消耗: 16.5 MB, 提交时间: 2024-02-19 09:57:25
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 t in words:
z = self.calc_z(t)
cur = root
for i, c in enumerate(t):
if c not in cur.son:
cur.son[c] = Node()
cur = cur.son[c]
if z[-1 - i] == i + 1: # t[-1-i:] == t[:i+1]
ans += cur.cnt
cur.cnt += 1
return ans
def calc_z(self, s: str) -> List[int]:
n = len(s)
z = [0] * n
l, r = 0, 0
for i in range(1, n):
if i <= r:
z[i] = min(z[i - l], r - i + 1)
while i + z[i] < n and s[z[i]] == s[i + z[i]]:
l, r = i, i + z[i]
z[i] += 1
z[0] = n
return z
golang 解法, 执行用时: 3 ms, 内存消耗: 5.1 MB, 提交时间: 2024-02-19 09:55:56
// Z函数 + 字典树
func calcZ(s string) []int {
n := len(s)
z := make([]int, n)
l, r := 0, 0
for i := 1; i < n; i++ {
if i <= r {
z[i] = min(z[i-l], r-i+1)
}
for i+z[i] < n && s[z[i]] == s[i+z[i]] {
l, r = i, i+z[i]
z[i]++
}
}
z[0] = n
return z
}
func countPrefixSuffixPairs(words []string) (ans int) {
type node struct {
son [26]*node
cnt int
}
root := &node{}
for _, t := range words {
z := calcZ(t)
cur := root
for i, c := range t {
c -= 'a'
if cur.son[c] == nil {
cur.son[c] = &node{}
}
cur = cur.son[c]
if z[len(t)-1-i] == i+1 { // t[:i+1] == t[len(t)-1-i:]
ans += cur.cnt
}
}
cur.cnt++
}
return
}
golang 解法, 执行用时: 6 ms, 内存消耗: 4.4 MB, 提交时间: 2024-02-19 09:54:11
func countPrefixSuffixPairs(words []string) (ans int) {
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 += cur.cnt
}
cur.cnt++
}
return
}
python3 解法, 执行用时: 44 ms, 内存消耗: 16.5 MB, 提交时间: 2024-02-19 09:50:21
# 字典树， __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
python3 解法, 执行用时: 43 ms, 内存消耗: 16.5 MB, 提交时间: 2024-02-19 09:45:04
class Solution:
def countPrefixSuffixPairs(self, words: List[str]) -> int:
c = Counter()
ans = 0
for w in words:
for k, v in c.items():
if w.startswith(k) and w.endswith(k):
ans += v
c[w] += 1
return ans