面试题17.13.恢复空间来源：LeetCodehttps://leetcode-cn.com/problems/re-space-lcci题目哦，不！您不小心删除了一篇长文章中的空格、标点符号和小写字母。诸如“我重置了计算机。它仍然没有启动！”之类的句子。已成为“irsetthecomputeritstilldidntboot”。在处理标点符号和大写字母之前，您必须将其分解为单词。当然，你有一本厚厚的字典，但有些词字典里没有。假设文章是用句子表示的，设计一个算法将文章断开，要求不识别字符的数量最少，返回不识别字符的数量。注：本题对原题稍作修改，只返回无法识别字符的个数示例：输入：dictionary=["looked","just","like","her","brother"]sentence="jesslookedjustliketimherbrother”输出：7解释：断句后是“jesslookedjustliketimherbrother”，一共7个无法识别的字符。Tip:0<=len(sentence)<=1000字典中的字符总数不超过150000。你可以认为字典和句子只包含小写字母。解题思路：动态规划先定义状态，让dp[i]表示字符串中前i个字符中不识别字符的最少个数。现在让我们谈谈状态转换。这里讨论的情况是：当确定前i-1个字符时，如果第i个字符不能与前面的子串成词，则说明第i个字符无法匹配。此时，第i个字符被视为无法识别的字符数，则dp[i]=dp[i-1]+1；现在讨论第i个字符能匹配到前一个子串且存在于字典中的情况：遍历前i个字符，如果从索引j到第i个字符串的末尾有字符串存入字典，则dp[i]=min(dp[i],dp[j])，维护和更新dp[i]。具体代码见【代码实现】。在上面的动态规划中，当需要判断第i个字符是否可以匹配到前面的子串时，需要每次遍历前i个字符，判断是否存在从索引j开始到结束的字符串第i个字符并且存在于字典中。这里会消耗大量的时间。官方的解决方案提供了使用【字典树】进行优化的思路。这里留空（字典树我还不精通，以后有机会再补充这方面的内容，欢迎指导交流。）[str],sentence:str)->int:length=len(sentence)dp=[0]*(length+1)foriinrange(1,length+1):#首先，第i个字符不能默认匹配，简化操作dp[i]=dp[i-1]+1#尝试查找从索引j到第i个字符的字符串是否可以在字典中形成为jinrange(i):ifsentence[j:i]indictionary:dp[i]=min(dp[i],dp[j])returndp[length]实现结果总结首先定义状态，让dp[i]是前i个字符中未识别字符的最少数量；状态转移，分情况讨论：假设判断第i-1个字符的情况，首先考虑第i个字符不能与前一个子串成词时，说明第i个字符不能与前一个子串成词匹配。此时第i个字符被认为是无法识别的字符数。然后dp[i]=dp[i-1]+1;当第i个字符能匹配到前面的子串并且存在于字典中时：遍历前i个字符，如果存在从索引j开始的第i个字符串结尾的字符串存入字典，则dp[i]=min(dp[i],dp[j])，维护和更新dp[i]。字典树可用于优化。（不是很熟练，暂时留空）欢迎关注公众号【图书收藏】
