LeetCode 题解工作台
统计前后缀下标对 I
给你一个下标从 0 开始的字符串数组 words 。 定义一个 布尔 函数 isPrefixAndSuffix ，它接受两个字符串参数 str1 和 str2 ： 当 str1 同时是 str2 的前缀（ prefix ）和后缀（ suffix ）时， isPrefixAndSuffix(str1,…
6
题型
5
代码语言
3
相关题
当前训练重点
简单 · 数组·string
答案摘要
我们可以枚举所有的下标对 $(i, j)$，其中 $i \lt j$，然后判断 `words[i]` 是否是 `words[j]` 的前缀和后缀，若是则计数加一。 时间复杂度 $O(n^2 \times m)$，其中 和 分别为 `words` 的长度和字符串的最大长度。
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 <= 501 <= words[i].length <= 10words[i]仅由小写英文字母组成。
解题思路
方法一：枚举
我们可以枚举所有的下标对 ，其中 ，然后判断 words[i] 是否是 words[j] 的前缀和后缀，若是则计数加一。
时间复杂度 ，其中 和 分别为 words 的长度和字符串的最大长度。
class Solution:
def countPrefixSuffixPairs(self, words: List[str]) -> int:
ans = 0
for i, s in enumerate(words):
for t in words[i + 1 :]:
ans += t.endswith(s) and t.startswith(s)
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(n^2 * m) because each of the n words is compared with every other word, and checking prefix and suffix takes O(m) time where m is the word length. Space complexity is O(n * m) for storing precomputed hashes or trie nodes. |
| 空间 | O(n \cdot m) |
面试官常问的追问
外企场景- question_mark
Mentions combining array iteration with string checks for prefix and suffix patterns.
- question_mark
Asks how to handle repeated strings efficiently in nested loops.
- question_mark
Looks for solutions that can leverage string structures like trie or hash maps.
常见陷阱
外企场景- error
Forgetting to exclude pairs where i equals j.
- error
Checking only prefix or only suffix instead of both simultaneously.
- error
Not accounting for overlapping prefixes and suffixes correctly when strings are identical or nested.
进阶变体
外企场景- arrow_right_alt
Count prefix-suffix pairs with variable-length substring matching instead of full word.
- arrow_right_alt
Extend to allow wildcards in prefix or suffix for pattern matching.
- arrow_right_alt
Find all pairs in larger arrays efficiently using rolling hash or trie optimizations.