LeetCode 题解工作台
单词替换
在英语中，我们有一个叫做 词根 (root) 的概念，可以词根 后面 添加其他一些词组成另一个较长的单词——我们称这个词为 衍生词 ( derivative )。例如，词根 help ，跟随着 继承 词 "ful" ，可以形成新的单词 "helpful" 。 现在，给定一个由许多 词根 组成的词典 …
4
题型
6
代码语言
3
相关题
当前训练重点
中等 · 数组·哈希·扫描
答案摘要
我们可以使用前缀树来存储词典中的所有词根。定义前缀树节点类 ，其中包含一个长度为 的数组 来存储子节点，以及一个布尔变量 来标记是否为一个完整的词根。 对于每个词根，我们将其插入前缀树中。对于句子中的每个单词，我们在前缀树中搜索其最短的词根，如果找到了，则替换该单词，否则保持不变。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·哈希·扫描 题型思路
题目描述
在英语中，我们有一个叫做 词根(root) 的概念，可以词根 后面 添加其他一些词组成另一个较长的单词——我们称这个词为 衍生词 (derivative)。例如，词根 help，跟随着 继承词 "ful"，可以形成新的单词 "helpful"。
现在，给定一个由许多 词根 组成的词典 dictionary 和一个用空格分隔单词形成的句子 sentence。你需要将句子中的所有 衍生词 用 词根 替换掉。如果 衍生词 有许多可以形成它的 词根，则用 最短 的 词根 替换它。
你需要输出替换之后的句子。
示例 1：
输入：dictionary = ["cat","bat","rat"], sentence = "the cattle was rattled by the battery" 输出："the cat was rat by the bat"
示例 2：
输入：dictionary = ["a","b","c"], sentence = "aadsfasf absbs bbab cadsfafs" 输出："a a b c"
提示：
1 <= dictionary.length <= 10001 <= dictionary[i].length <= 100dictionary[i]仅由小写字母组成。1 <= sentence.length <= 106sentence仅由小写字母和空格组成。sentence中单词的总量在范围[1, 1000]内。sentence中每个单词的长度在范围[1, 1000]内。sentence中单词之间由一个空格隔开。sentence没有前导或尾随空格。
解题思路
方法一：前缀树
我们可以使用前缀树来存储词典中的所有词根。定义前缀树节点类 ，其中包含一个长度为 的数组 来存储子节点，以及一个布尔变量 来标记是否为一个完整的词根。
对于每个词根，我们将其插入前缀树中。对于句子中的每个单词，我们在前缀树中搜索其最短的词根，如果找到了，则替换该单词，否则保持不变。
时间复杂度 ，空间复杂度 ，其中 和 分别是词典中词根的数量和平均长度，而 是句子中单词的总长度。
class Trie:
def __init__(self):
self.children = [None] * 26
self.is_end = False
def insert(self, w: str) -> None:
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.is_end = True
def search(self, w: str) -> str:
node = self
for i, c in enumerate(w, 1):
idx = ord(c) - ord("a")
if node.children[idx] is None:
return w
node = node.children[idx]
if node.is_end:
return w[:i]
return w
class Solution:
def replaceWords(self, dictionary: List[str], sentence: str) -> str:
trie = Trie()
for w in dictionary:
trie.insert(w)
return " ".join(trie.search(w) for w in sentence.split())
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | O(d \cdot w + s \cdot w) |
| 空间 | O(d \cdot w + s \cdot w) |
面试官常问的追问
外企场景- question_mark
Tests understanding of efficient string matching and optimization techniques.
- question_mark
Tests familiarity with hash tables and efficient lookup methods.
- question_mark
Evaluates the ability to handle large input sizes and optimize for time and space complexity.
常见陷阱
外企场景- error
Overlooking edge cases such as words that have no matching root.
- error
Incorrectly handling cases where multiple roots can match, not picking the shortest.
- error
Not optimizing the search for roots, leading to slower solutions.
进阶变体
外企场景- arrow_right_alt
Use a trie instead of a hash table to optimize root lookup.
- arrow_right_alt
Limit the dictionary size or impose stricter constraints on the sentence.
- arrow_right_alt
Allow multiple words to be replaced by multiple roots (e.g., handle word sequences).