LeetCode 题解工作台
统计前后缀下标对 II
给你一个下标从 0 开始的字符串数组 words 。 定义一个 布尔 函数 isPrefixAndSuffix ，它接受两个字符串参数 str1 和 str2 ： 当 str1 同时是 str2 的前缀（ prefix ）和后缀（ suffix ）时， isPrefixAndSuffix(str1,…
6
题型
5
代码语言
3
相关题
当前训练重点
困难 · 数组·string
答案摘要
我们可以把字符串数组中的每个字符串 当作一个字符对的列表，其中每个字符对 $(s[i], s[m - i - 1])$ 表示字符串 的前缀和后缀的第 个字符对。 我们可以使用字典树来存储所有的字符对，然后对于每个字符串 ，我们在字典树中查找所有的字符对 $(s[i], s[m - i - 1])$，并将其计数加到答案中。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·string 题型思路
题目描述
给你一个下标从 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。
解题思路
方法一：字典树
我们可以把字符串数组中的每个字符串 当作一个字符对的列表，其中每个字符对 表示字符串 的前缀和后缀的第 个字符对。
我们可以使用字典树来存储所有的字符对，然后对于每个字符串 ，我们在字典树中查找所有的字符对 ，并将其计数加到答案中。
时间复杂度 ，空间复杂度 。其中 和 分别为 words 的长度和字符串的最大长度。
class Node:
__slots__ = ["children", "cnt"]
def __init__(self):
self.children = {}
self.cnt = 0
class Solution:
def countPrefixSuffixPairs(self, words: List[str]) -> int:
ans = 0
trie = Node()
for s in words:
node = trie
for p in zip(s, reversed(s)):
if p not in node.children:
node.children[p] = Node()
node = node.children[p]
ans += node.cnt
node.cnt += 1
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity depends on the approach: brute-force is O(n^2 * k), Trie-based is roughly O(n * k) with efficient lookups, and rolling hash reduces per comparison cost further. Space complexity includes storing Tries and hash arrays, which is O(total characters in words). |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Do you consider both prefix and suffix simultaneously?
- question_mark
Are you using a Trie or hash to avoid full string comparisons?
- question_mark
How would you scale if words array has 100000 entries?
常见陷阱
外企场景- error
Attempting only prefix checks and ignoring suffix validation.
- error
Using nested loops without optimization leading to TLE.
- error
Not handling edge cases where a word is equal to another word completely.
进阶变体
外企场景- arrow_right_alt
Count only prefix pairs without suffix requirement.
- arrow_right_alt
Check for strict proper prefix and proper suffix excluding full equality.
- arrow_right_alt
Find pairs where the combined length equals a target number.