LeetCode 648中等Trie
单词替换 图解题解
这道题到底在问什么
给一个由词根组成的词典 dictionary 和一个用空格分隔的句子 sentence。把句子里所有由词根派生出的衍生词换成词根;有多个词根能形成它,用最短那个;找不到词根就保留原词。
- dictionary
- ["cat","bat","rat"]
- sentence
- "the cattle was rattled by the battery"
- 输出
- "the cat was rat by the bat"
最优解：一步一步想明白
- 3下面先把词根 cat / bat / rat 建成 Trie,看它怎么按字符分叉、在词根末尾打结束标记;再拿句子逐词去 Trie 里走。
- 4root → c从空 Trie 的根 root 出发,插入 cat 的第 1 个字符 c:根下挂出一个 c 节点(橙色是刚走到的边)。
- 5c → a沿 c 继续往下挂 a 节点(c-a 是同一条链)。蓝色是已经走过的字符边。
- 6a → t,打结束标记挂上 t 并在末尾打结束标记 ★(绿色)——表示 cat 是一个完整词根。一条 root→c→a→t★ 的链就建好了。
- 7三条链共用 root把 bat、rat 也插进来:它们各自从 root 分出一条链(c… / b… / r…),末尾都打上★。三个绿色 t★ 就是三个词根的终点。
- 8word = cattle,从 root 起处理第一个有词根的单词 cattle。游标 node 站在 Trie 的 root,prefix 从空串开始,准备逐字符往下走。
- 9root 有 c 边 → 下行读 cattle[0]=c,root 下正好有 c 边,游标下行到 c 节点。c 节点没有★,还不是词根,继续。
- 10c 有 a 边 → 下行读 cattle[1]=a,c 下有 a 边,继续下行到 a。prefix="ca",a 节点仍没有★。
- 11a→t★,命中词根 cat读 cattle[2]=t,走到 t 节点上有★!命中词根 cat,立刻停——后面 tle 不用再看。绿色前三格就是替换结果。
- 12word = the,root 起再看一个没有词根的单词 the(它在 cattle 前面,这里补看一下)。游标回到 root。
- 13root 下没有 t 边读 the[0]=t,可 root 下只有 c/b/r 三条边、没有 t 边!游标卡在 root 下不去,the 找不到任何词根,原样保留。
- 14word = rattled,root 起处理 rattled。游标回到 root,prefix 清空,准备走 r 那条链。
- 15root 有 r 边 → 下行读 rattled[0]=r,root 下有 r 边,下行到 r 节点。还没★,继续。
- 16r 有 a 边 → 下行读 rattled[1]=a,r 下有 a 边,下行。prefix="ra",仍无★。
- 17a→t★,命中词根 rat读 rattled[2]=t,t 节点带★!命中词根 rat,停。后面 tled 丢掉,rattled 替换成 rat。
- 18word = battery,root 起处理最后一个有词根的单词 battery。游标回 root,走 b 那条链。
- 19root 有 b 边 → 下行读 battery[0]=b,root 下有 b 边,下行到 b。无★,继续。
- 20b 有 a 边 → 下行读 battery[1]=a,b 下有 a 边,下行。prefix="ba",仍无★。
- 21a→t★,命中词根 bat读 battery[2]=t,t 带★!命中词根 bat,停。battery 替换成 bat。
- 22the cat was …把每个词的结果按原顺序填回去:the 保留、cattle 换 cat、was 保留。绿色格子是被替换的词根。
- 23… rat by the bat继续填:rattled 换 rat、by 与 the 保留、battery 换 bat。三个绿色词根全部就位。
- 24join → 最终句子七个词依次连成新句子,用空格拼起来返回 "the cat was rat by the bat"——cattle/rattled/battery 各自被最短词根替换,其余原样保留。
- 27记住骨架:建 Trie + 结束标记 → 单词从 root 逐字符下行 → 走不通 break / 踩 ★ break。
完整代码（Python / C++ / Java）
Python
class Solution:
def replaceWords(self, dictionary, sentence):
# 建 Trie:每层一个 dict,'#' 标记词根结束
trie = {}
for w in dictionary:
node = trie
for ch in w:
node = node.setdefault(ch, {})
node['#'] = w # 结束标记,存词根本身
ans = []
for word in sentence.split():
node, prefix = trie, ''
replaced = word
for ch in word:
if ch not in node: # 走不下去
break
node = node[ch]; prefix += ch
if '#' in node: # 踩到结束标记
replaced = prefix; break
ans.append(replaced)
return ' '.join(ans)C++
class Solution {
struct Node { Node* ch[26] = {}; bool end = false; };
public:
string replaceWords(vector<string>& dictionary, string sentence) {
Node* root = new Node();
for (auto& w : dictionary) { // 建 Trie
Node* node = root;
for (char c : w) {
int k = c - 'a';
if (!node->ch[k]) node->ch[k] = new Node();
node = node->ch[k];
}
node->end = true;
}
istringstream iss(sentence); string word, result; bool first = true;
while (iss >> word) {
Node* node = root; string prefix, replaced = word;
for (char c : word) {
int k = c - 'a';
if (!node->ch[k]) break; // 走不下去
node = node->ch[k]; prefix += c;
if (node->end) { replaced = prefix; break; }
}
if (!first) result += ' '; first = false;
result += replaced;
}
return result;
}
};Java
class Solution {
static class Node { Node[] ch = new Node[26]; boolean end; }
public String replaceWords(List<String> dictionary, String sentence) {
Node root = new Node();
for (String w : dictionary) { // 建 Trie
Node node = root;
for (char c : w.toCharArray()) {
int k = c - 'a';
if (node.ch[k] == null) node.ch[k] = new Node();
node = node.ch[k];
}
node.end = true;
}
StringBuilder sb = new StringBuilder();
for (String word : sentence.split(" ")) {
Node node = root; StringBuilder prefix = new StringBuilder();
String replaced = word;
for (char c : word.toCharArray()) {
int k = c - 'a';
if (node.ch[k] == null) break; // 走不下去
node = node.ch[k]; prefix.append(c);
if (node.end) { replaced = prefix.toString(); break; }
}
if (sb.length() > 0) sb.append(' ');
sb.append(replaced);
}
return sb.toString();
}
}复杂度
O(D + S)
O(D)
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 单词替换 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
为什么用 Trie 而不是把词根放 set 逐前缀查?+
set 法每个单词要对每个前缀做一次哈希查询(前缀串还要反复构造);Trie 把所有词根共享公共前缀,查词时沿边一次性下行,每字符 O(1),整体 O(D+S),且天然「踩到结束标记即最短」。
命中后为什么能立刻 break?+
前缀沿 root 逐字符变长,短词根的结束标记在树上更浅、必先被踩到,第一次命中即最短,无需继续。
单词某个字符在当前节点没有子边怎么办?+
说明这条前缀路径不存在,该单词没有任何词根前缀,直接 break 并保留原单词。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄把 单词替换 一步步讲透（全站已上线 905 份讲透，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
把这道题真正拿下
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。