# \[面试题 17.13]\[中等]\[动态规划]\[前缀树] 恢复空格

## 题目描述

[面试题 17.13. 恢复空格](https://leetcode-cn.com/problems/re-space-lcci/)

哦，不！你不小心把一个长篇文章中的空格、标点都删掉了，并且大写也弄成了小写。像句子"I reset the computer. It still didn’t boot!"已经变成了"iresetthecomputeritstilldidntboot"。在处理标点符号和大小写之前，你得先把它断成词语。当然了，你有一本厚厚的词典dictionary，不过，有些词没在词典里。假设文章用sentence表示，设计一个算法，把文章断开，要求未识别的字符最少，返回未识别的字符数。

注意：本题相对原题稍作改动，只需返回未识别的字符数

示例：

```
输入：
dictionary = ["looked","just","like","her","brother"]
sentence = "jesslookedjustliketimherbrother"
输出： 7
解释： 断句后为"jess looked just like tim her brother"，共7个未识别字符。
```

提示：

* 0 <= len(sentence) <= 1000
* dictionary中总字符数不超过 150000。
* 你可以认为dictionary和sentence中只包含小写字母。

## 解题思路

使用动态规划思路. 状态定义为题目中的定义, `dp[i]`表示`[0, i]`子串中, 未识别的字符数. 最后的结果为`dp[-1]`.

考虑状态转移方程, 分为以下情况:

* 字符`s[i]`无法自身, 或者与之前相连的任何一个子串组成一个单词时, `s[i]`无法被识别, `dp[i]=dp[i-1]+1`
* 字符`s[i]`可以与前面某个子串组成一个单词时, 假设`[j,i]`代表这个单词
  * 相当于`[j,i]`子串不会对未识别字符数量做贡献, 相应的`dp[i]=dp[j-1]`
  * 但需要考虑将`[j,i]`真的作为一个单词是否合适. 考虑字符串`abcde`及字典`['abcd', 'de']`, 对于字符`e`, 如果将`de`作为最终的单词, 那么前面的`abc`就不再是一个词了, 对应的`dp[4]=3`; 但明显`abcd`作为一个单词, 只剩一个`e`, 这种情况下对应的`dp[4]=1`, 是更合适的
  * 再度观察这个例子, 在`i=3`时, 我们得到`dp[3]=0`. 在考虑`dp[4]`时, 无论如何, 我们都要考虑`s[i]`不组成单词的情况, 因为这也是一种最优解的情况

考虑以上情况, 在求`dp[i]`时, 我们首先由`dp[i]=dp[i-1]+1`得到`s[i]`不组成单词的情况, 然后从`i`开始, 向前遍历, 得到所有以`s[i]`结尾, 且是单词的子串, 根据`dp[i]=dp[j-1]`得到`[j,i]`这个单词对应的结果, 然后用`min(dp[i], dp[j-1])`判别是否应该采纳, 其中初始的`dp[1]`为`dp[i]=dp[i-1]+1`. 如果采纳, 更新`dp[i]`, `j`继续向前寻找可能存在的更长的单词.

但这样寻找单词, 会一直寻找到`j=0`, 当`i`较大时, 是比较耗时的. 我们可以结合**前缀树**进行减值. 说是前缀树, 但在本题中, 是将所有字典中的单词倒过来以构建这棵树. 因为我们查找单词时, 是从后向前逐步覆盖某个单词的. 如果在查找时, 发现某个子串已经不在前缀树中, 就可以停止了. 以此完成剪枝, 提高搜索效率.

整体代码如下, 前缀树`Trie`树借助嵌套的字典实现.

```python
class Trie:
    def __init__(self):
        self.root = dict()

    def insert(self, word):
        root = self.root
        for c in word[::-1]:
            new_dict = dict()
            cur_dict = root.get(c, new_dict)
            root[c] = cur_dict
            root = cur_dict

    def search(self, word):
        root = self.root
        for c in word[::-1]:
            if c not in root:
                return False
            root = root[c]
        return True


class Solution:
    def respace(self, dictionary: List[str], sentence: str) -> int:
        dic = set(dictionary)
        trie = Trie()
        for word in dictionary:
            trie.insert(word)

        n = len(sentence)
        if n == 0:
            return 0

        dp = [0] * n
        for i in range(n):
            dp[i] = 1 + (dp[i - 1] if i > 0 else 0)
            for j in range(i, -1, -1):
                t_word = sentence[j: i + 1]
                if trie.search(t_word):
                    if t_word in dic:
                        dp[i] = min(dp[i], dp[j - 1] if j > 0 else 0)
                else:
                    break
        return dp[-1]
```