LeetCode 题解工作台
字符串的前缀分数和
给你一个长度为 n 的数组 words ，该数组由 非空 字符串组成。 定义字符串 term 的 分数 等于以 term 作为 前缀 的 words[i] 的数目。 例如，如果 words = ["a", "ab", "abc", "cab"] ，那么 "ab" 的分数是 2 ，因为 "ab" 是 …
4
题型
6
代码语言
3
相关题
当前训练重点
困难 · 数组·string
答案摘要
我们可以用前缀树来维护所有字符串的前缀以及每个前缀出现的次数。 定义前缀树节点结构体 `Trie`，包含两个属性：
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·string 题型思路
题目描述
给你一个长度为 n 的数组 words ，该数组由 非空 字符串组成。
定义字符串 term 的 分数 等于以 term 作为 前缀 的 words[i] 的数目。
- 例如，如果
words = ["a", "ab", "abc", "cab"]，那么"ab"的分数是2，因为"ab"是"ab"和"abc"的一个前缀。
返回一个长度为 n 的数组 answer ，其中 answer[i] 是 words[i] 的每个非空前缀的分数 总和 。
注意：字符串视作它自身的一个前缀。
示例 1：
输入：words = ["abc","ab","bc","b"] 输出：[5,4,3,2] 解释：对应每个字符串的答案如下： - "abc" 有 3 个前缀："a"、"ab" 和 "abc" 。 - 2 个字符串的前缀为 "a" ，2 个字符串的前缀为 "ab" ，1 个字符串的前缀为 "abc" 。 总计 answer[0] = 2 + 2 + 1 = 5 。 - "ab" 有 2 个前缀："a" 和 "ab" 。 - 2 个字符串的前缀为 "a" ，2 个字符串的前缀为 "ab" 。 总计 answer[1] = 2 + 2 = 4 。 - "bc" 有 2 个前缀："b" 和 "bc" 。 - 2 个字符串的前缀为 "b" ，1 个字符串的前缀为 "bc" 。 总计 answer[2] = 2 + 1 = 3 。 - "b" 有 1 个前缀："b"。 - 2 个字符串的前缀为 "b" 。 总计 answer[3] = 2 。
示例 2：
输入：words = ["abcd"] 输出：[4] 解释： "abcd" 有 4 个前缀 "a"、"ab"、"abc" 和 "abcd"。 每个前缀的分数都是 1 ，总计 answer[0] = 1 + 1 + 1 + 1 = 4 。
提示：
1 <= words.length <= 10001 <= words[i].length <= 1000words[i]由小写英文字母组成
解题思路
方法一：前缀树
我们可以用前缀树来维护所有字符串的前缀以及每个前缀出现的次数。
定义前缀树节点结构体 Trie，包含两个属性：
children：长度为 26 的数组，用于存储当前节点的子节点。cnt：当前节点的出现次数。
定义前缀树的两个方法：
insert：插入一个字符串，将其前缀插入前缀树。search：搜索一个字符串，返回其前缀的出现次数。
我们遍历所有字符串，将每个字符串插入前缀树中。然后再遍历所有字符串，对每个字符串调用 search 方法，累加每个前缀的出现次数即可。
时间复杂度 ，空间复杂度 ，其中 是所有字符串的总长度。
class Trie:
__slots__ = "children", "cnt"
def __init__(self):
self.children = [None] * 26
self.cnt = 0
def insert(self, w):
node = self
for c in w:
idx = ord(c) - ord("a")
if node.children[idx] is None:
node.children[idx] = Trie()
node = node.children[idx]
node.cnt += 1
def search(self, w):
node = self
ans = 0
for c in w:
idx = ord(c) - ord("a")
if node.children[idx] is None:
return ans
node = node.children[idx]
ans += node.cnt
return ans
class Solution:
def sumPrefixScores(self, words: List[str]) -> List[int]:
trie = Trie()
for w in words:
trie.insert(w)
return [trie.search(w) for w in words]
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | O(N \cdot M) |
| 空间 | O(N \cdot M) |
面试官常问的追问
外企场景- question_mark
The candidate should be able to recognize the importance of trie data structures in solving this problem efficiently.
- question_mark
Look for an explanation of how the trie helps track prefix counts, and ensure the candidate understands how it avoids redundant calculations.
- question_mark
The candidate should demonstrate an understanding of both array manipulation and string handling while solving this problem.
常见陷阱
外企场景- error
Not using a trie can lead to inefficient solutions that directly compare prefixes for each word, leading to high time complexity.
- error
Failing to reuse previously computed prefix scores for efficiency, resulting in redundant work and unnecessary complexity.
- error
Not properly handling edge cases where a word has very few or very long prefixes.
进阶变体
外企场景- arrow_right_alt
Modify the problem to only calculate prefix scores for specific prefixes of each word.
- arrow_right_alt
Extend the problem to allow for case-sensitive strings or strings with non-alphabetic characters.
- arrow_right_alt
Alter the problem to ask for the number of words with each exact prefix rather than the sum of prefix scores.