题目来源：力扣（LeetCode）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] 表示字符串中前 i 个字符的最少未识别字符数。
现在说一下状态转移，这里分情况讨论：
- 当确定前面 i-1 个字符时，如果第 i 个字符，无法与前面的子串组成单词时，也就代表第 i 个字符无法匹配，此时第 i 个字符当成一个未识别的字符数，那么 dp[i] = dp[i-1] + 1；
- 现在讨论第 i 个字符可以跟前面子串匹配存在于 dictionary 的情况：
- 遍历前 i 个字符，若存在以索引 j 开始到第 i 个字符串结尾的字符串存储于字典中，那么 dp[i] = min(dp[i], dp[j])，维护更新 dp[i]。
具体的代码见【代码实现】。
上面的动态规划中，当需要确定第 i 个字符是否能够与前面的子串进行匹配时，每次都需要遍历前 i 个字符，判断是否存在以索引 j 开始到第 i 个字符结尾的字符串且存在于词典中。这里会消耗大量的时间。
官方题解提供使用【字典树】的思路进行优化。这里 暂留空（对于字典树还不熟练，后续有机会补充这方面的内容，欢迎指导交流。）
代码实现class Solution:
def respace(self, dictionary: List[str], sentence: str) -> int:
length = len(sentence)
dp = [0] * (length + 1)
for i in range(1, length + 1):
# 先默认第 i 个字符无法匹配，简化操作
dp[i] = dp[i-1] + 1
# 尝试查找是否存在索引 j 开始到第 i 个字符能够组成的字符串存在于词典中
for j in range(i):
if sentence[j:i] in dictionary:
dp[i] = min(dp[i], dp[j])
return dp[length]
总结
- 先进行状态定义，设 dp[i] 为前 i 个字符中最少未识别字符数；
- 状态转移，分情况讨论：
- 假设确定前 i-1 个字符的情况，先考虑第 i 个字符无法与前面的子串组成单词时，也就代表第 i 个字符无法匹配，此时第 i 个字符当成一个未识别的字符数，那么 dp[i] = dp[i-1] + 1；
- 当第 i 个字符可以跟前面子串匹配且存在于 dictionary 的情况：
- 遍历前 i 个字符，若存在以索引 j 开始到第 i 个字符串结尾的字符串存储于字典中，那么 dp[i] = min(dp[i], dp[j])，维护更新 dp[i]。
- 可用字典树进行优化。（不太熟练，暂留空）
欢迎关注
