LeetCode 面试题 17.13. 恢复空格
题目描述
题意分析
在句子中重新划分单词，字典中的完整单词所覆盖的字符算已识别，其余字符算未识别，求未识别字符的最少数量。字典和句子只含小写字母；本题只返回数量，不需要还原具体断句或标点。
解法：逆序 Trie + 前缀 DP
核心思路
[!blue]
不同切分会反复遇到相同的句子前缀，因此定义
dp[i]为前i个字符的最少未识别数，空前缀dp[0] = 0。计算dp[i]时，先把最后一个字符视为未识别，得到保底值dp[i - 1] + 1。一段连续的未识别字符也可以逐个使用这种转移处理，不必另行枚举其长度。另一种可能是最后一段恰好为字典词。若半开区间
sentence[j:i]是一个完整词，这一段不增加未识别数，之前的前缀已经由dp[j]最优处理，因此候选值就是dp[j]。在所有以i为右边界的字典词中取最小值，就覆盖了全部可能的最后一段。为了高效找到这些结尾相同的词，将每个字典词从末字符向前插入 Trie。处理结尾
i时，也从sentence[i - 1]向左走，这样扫到j后，当前 Trie 路径恰好对应sentence[j:i]的逆序。到达wordEnd节点，就表示这段是完整字典词，可以用dp[j]更新。某个字符没有对应孩子时可以立即停止：所有更长候选都必须先经过已经失败的这段逆序前缀，不可能再成为字典词。命中一个词却不能直接停止，它可能还是更长字典词的后缀，需要继续比较不同起点带来的
dp[j]。只有当前dp[i]已经为零时，才达到不可能更小的下界，可以提前结束本轮。按
i从小到大计算，所有依赖的j < i都已经得到最优值。每个转移都对应合法的断句选择，而任何完整方案的末尾又必属于上述两类，所以最终dp[n]就是全句最优答案。句子为空时直接得到零；没有可匹配词时，保底转移会把所有字符计为未识别。
解题步骤
- 将字典词逆序插入 Trie，在每个词最后到达的节点标记
wordEnd。- 建立长度为
n + 1的前缀 DP，令空前缀费用为零。- 对每个前缀长度
i，先设dp[i] = dp[i - 1] + 1。- 从
i - 1向左沿 Trie 查找，路径断开就停止；遇到词终点，用dp[j]更新当前状态。- 当前值为零时停止继续匹配，全部前缀处理完后返回
dp[n]。
代码实现
class Solution {
public int respace(String[] dictionary, String sentence) {
TrieNode root = new TrieNode();
for (String word : dictionary) {
TrieNode node = root;
for (int i = word.length() - 1; i >= 0; i--) {
int index = word.charAt(i) - 'a';
if (node.children[index] == null) {
node.children[index] = new TrieNode();
}
node = node.children[index];
}
node.wordEnd = true;
}
int n = sentence.length();
int[] dp = new int[n + 1];
for (int i = 1; i <= n; i++) {
dp[i] = dp[i - 1] + 1;
TrieNode node = root;
for (int j = i - 1; j >= 0; j--) {
int index = sentence.charAt(j) - 'a';
node = node.children[index];
if (node == null) {
break;
}
if (node.wordEnd) {
dp[i] = Math.min(dp[i], dp[j]);
if (dp[i] == 0) {
break;
}
}
}
}
return dp[n];
}
private static class TrieNode {
private final TrieNode[] children = new TrieNode[26];
private boolean wordEnd;
}
}
type respaceTrieNode struct {
children [26]*respaceTrieNode
wordEnd bool
}
func respace(dictionary []string, sentence string) int {
root := &respaceTrieNode{}
for _, word := range dictionary {
node := root
for i := len(word) - 1; i >= 0; i-- {
index := int(word[i] - 'a')
if node.children[index] == nil {
node.children[index] = &respaceTrieNode{}
}
node = node.children[index]
}
node.wordEnd = true
}
n := len(sentence)
dp := make([]int, n+1)
for i := 1; i <= n; i++ {
dp[i] = dp[i-1] + 1
node := root
for j := i - 1; j >= 0; j-- {
index := int(sentence[j] - 'a')
node = node.children[index]
if node == nil {
break
}
if node.wordEnd {
dp[i] = min(dp[i], dp[j])
if dp[i] == 0 {
break
}
}
}
}
return dp[n]
}
复杂度分析
- 时间复杂度：$O(W+D+n(\min(n,L)+1))$，其中
W为字典词数、D为字典总字符数、n为句长、L为最长词长，空字典时L = 0。建树遍历词和字符，每个结尾最多沿 Trie 匹配可用的词长，再做一次失败检查。- 空间复杂度：$O(D+n+1)$，用于 Trie、根节点和包含空前缀的 DP 数组。
关键点总结
[!green]
dp[i]记录前i个字符的最少未识别数，匹配完整词时不增加费用。- 逆序建树与从结尾向左扫描方向一致，多个候选共享后缀比较。
- 路径断开可排除所有更长候选，命中单词则通常还要继续；零才是费用的提前终止下界。
易错点总结
[!yellow]
- 每轮必须设置未识别字符的保底值，不能把数组默认零当成该前缀已经完全识别。
- 只匹配到了 Trie 路径还不够，必须到达
wordEnd才能把整段按零费用处理。- 已识别区间
sentence[j:i]应接在dp[j]后，不能再加它的长度，也不能误读dp[j - 1]。- 不能只挑最长匹配词；它前面的最优断句费用未必更小，需比较所有可达词终点。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 139. 单词拆分 | 中等 | 同样按最后一个匹配词切分前缀，本题允许未识别字符并最小化它们的数量。 |
| 140. 单词拆分 II | 困难 | 同样利用字典匹配和前缀关系，原题输出所有完整切分，本题只求最少未识别数。 |