算法题：恢复空格

本文详细解释《程序员面试金典》中的《恢复空格》一题。

题目描述

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

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

输入：

dictionary = ["looked","just","like","her","brother"]

sentence = "jesslookedjustliketimherbrother"

输出：

解释：

断句后为jess looked just like tim her brother，共 7 个未识别字符。

提示：

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

分析

我们可以使用动态规划来解决这道题，dp[i] 表示在以索引 i 结尾的字符串中，它之前最多能匹配单词的数量。

需要注意的是，最后需要返回的是未识别的字符数，也就是没有匹配成功的字符数。因此，我们用字符串的总长度减去已经匹配完成的字符串长度，那么最后剩下的就是未识别的字符数。

如下所示：

刚开始来到索引为 0 的L位置，由于L不在字典中，因此，dp[0]=0。
来到索引为 1 的e位置，由于字符串e和Le都不在字典中，因此，dp[1]=0。
来到索引为 2 的e位置，由于字符串Lee、ee、e都不在字典中，因此，dp[2]=0。
来到索引为 3 的t位置，由于字符串Leet在字典中，并且还是最长的，因此，dp[3]=4。

接下来是索引为 4 的C位置，在以C结尾的字符串中，只有除了Leet可以从字典中匹配到以外，etc也是可以匹配到的。因此，dp[4]=3+dp[1]=3，其中，这里的 3 指的是etc字符串的长度，后面的 dp[1] 指的是以e结尾所能最多匹配单词的数量。虽然，我们看到 dp[4] 在当前是等于 3 的，但是仍然不能取，我们还应该考虑到字符串Leet，它的长度是 4，虽然不是以c结尾的，但是它出现在了字典中，并且当前的长度最长。所以，我们在这里需要取最大值，即 dp[4]=Math.max(3+dp[1], 4)。如下所示：

接下来是索引为 5 的o位置以及索引为 6 的d，它们的取值只能取到最大值 4。如下所示：

接下来是索引为 7 的e，此时code可以在字典中进行匹配。此时，dp[7]=Math.max(4, 4+dp[7-4])=8。其中，前面的 4 表示前一个位置所能表示的最大长度，而 4+dp[7-4] 表示以e结尾的、在字典中能够匹配的字符串code的长度为 4，e的当前位置是 7，然后将去code的长度，就是 dp[7-4]。如下图所示：