LeetCode 面试题 17.13. 恢复空格

2026-03-28 HGNULB 约 6 分钟

文章信息 3 个分类 7 个标签

分类

题目描述

✅ 面试题 17.13. 恢复空格

题意分析

给一个字典和一段去掉空格的句子，可以在任意位置切分；字典词覆盖的字符算已识别，其余字符算未识别，目标是最小化未识别字符数。

切分方案指数级，瓶颈是同一个前缀会被不同切法反复求解。自然状态是 dp[i]：sentence 前 i 个字符的最少未识别数。

对每个结尾 i，有两类决策：把第 i 个字符当作未识别，得到 dp[i-1]+1；或者选择一个以 i 结尾的字典词 sentence[j:i]，得到 dp[j]。为了避免为每个 j 创建子串并查哈希，使用“逆序字典树”：把字典词倒着插入，从 i-1 向左扫描即可同时枚举所有以 i 结尾的词。

解法：逆序 Trie + 前缀 DP

核心思路

dp[0]=0。计算 dp[i] 时先取保底值 dp[i-1]+1，表示当前字符不属于任何识别词。

随后从 j=i-1 向左沿逆序 Trie 走 sentence[j]。路径断开说明更长后缀也不可能在字典中，可以立即停止；到达单词终点时，用 dp[j] 更新 dp[i]。

不变量是：完成 i 后，dp[i] 已覆盖所有可能的最后一段——最后一个字符未识别，或最后一段是任意一个以 i 结尾的字典词。因此状态转移既不漏也不重。

例：字典 ["looked","just","like","her","brother"]，句子 "jesslookedjustliketimherbrother"。DP 会识别 looked、just、like、her、brother，"jess" 四个字符和 "tim" 三个字符只能走未识别转移，最终答案为 7。

解题步骤

把每个字典词从后向前插入 Trie，并在词首对应节点标记终点。

创建 dp[0..n]，dp[0]=0。

对 i 从 1 到 n，先令 dp[i]=dp[i-1]+1。

从 j=i-1 向 0 扫描，沿 Trie 查 sentence[j]；路径不存在就 break。

遇到词终点，用 dp[j] 更新 dp[i]；若已经为 0 可提前结束。

返回 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(D + nL)，D 是字典总字符数，L 是最长字典词长度。每个结尾最多沿 Trie 向左走 L 步。

空间复杂度：O(D + n)，Trie 节点总数不超过 D，DP 数组长度 n+1。

关键点总结

dp 的含义是“前 i 个字符最少未识别数”，不是识别词数量。

保底转移 dp[i-1]+1 保证即使没有任何字典词也有合法答案。

逆序 Trie 与“枚举以 i 结尾的词”方向一致，路径断开即可剪枝。

面试追问若要求还原加空格后的句子，可给 dp 增加前驱下标与“本段是否识别”的记录，最后从 n 反向恢复。

易错点总结

dp 默认全 0，不设置保底值：字典为空时会错误返回 0；句子每个字符都应未识别，正确答案是 n。

字典正序建 Trie、句子却从右向左查：第一步就沿错方向，所有词都匹配不到。

命中字典词后写成 dp[i]=dp[j]+(i-j)：把已识别单词长度又算成未识别，失去匹配意义。

路径不存在仍继续向左：更长后缀不可能重新接回 Trie，只会浪费时间，甚至对 null 解引用。

只尝试最长匹配词：局部最长不保证全局最优；短词可能与后续词组合出更少未识别字符，必须由 DP 比较所有可达终点。

相似题目

题目	难度	考察点
139. 单词拆分	中等	判断能否全部识别的布尔 DP
140. 单词拆分 II	困难	恢复所有合法切分方案
208. 实现 Trie	中等	字典树基础结构