题目难度: 中等

原题链接[1]

今天继续更新程序员面试金典系列, 大家在公众号 算法精选 里回复 面试金典 就能看到该系列当前连载的所有文章了, 记得关注哦~

题目描述

哦，不！你不小心把一个长篇文章中的空格、标点都删掉了，并且大写也弄成了小写。像句子"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) <= 1000dictionary 中总字符数不超过 150000。你可以认为 dictionary 和 sentence 中只包含小写字母。题目思考如何计算并维护最小的未识别字符数?解决方案思路分析题目, 如果我们可以计算出任意起点下标 i 开始的子字符串的最小未识别字符数, 记作 dp[i]那么显然整体的最小未识别字符数就是 dp[0]以上就是典型的动态规划的思想, 利用前面的计算结果来推导出当前的结果那如何计算 dp[i]呢? 首先初始化 dp[n]=0, 因为空字符串的最小未识别字符数显然是 0然后从后向前遍历, 针对 dp[i] 而言, 它后面的所有 dp 值都已经计算好了那么我们就可以遍历大于 i 的每个下标 j, 检查 i 到 j 的部分 [i,j) (左闭右开区间) 是否在字典内在的话就不会增加未识别字符, 否则增加 j-i 个未识别字符上述过程对应的转移方程就是: 假设 i 到 j 增加的未识别字符是 unidentified那么就有 dp[i] = min(dp[j]+unidentified) (j 取值范围是[i+1,n])另外, 我们可以先将输入的字典转成集合, 这样可以降低检查子串是否在字典的时间复杂度下面代码有详细的注释, 方便大家理解复杂度时间复杂度 O(N^2*M): 假设 N 是 sentence 长度, M 是字典中的字符串的平均长度, 需要两层遍历找最小 dp 值 (O(N^2)), 而查找字符串的复杂度是 O(M)空间复杂度 O(N+C): 假设 N 是 sentence 长度, C 是字典中的总字符数, 记忆化搜索的缓存空间是 O(N), 将字典列表转成字符串集合的空间是 O(C)代码

class Solution:    def respace(self, dictionary: List[str], sentence: str) -> int:        # 动态规划+字符串集合        # 先将给定的字典列表转成集合, 降低查找的时间复杂度        dictionary = set(dictionary)        n = len(sentence)        # 初始化未识别字符数为最大值        dp = [n] * (n + 1)        # 空字符串时未识别字符数为0        dp[n] = 0        for i in range(n)[::-1]:            # 逆序求dp值            for j in range(i + 1, n + 1):                # 如果sentence[i:j]在字典中, 则可以直接使用它, 此时未识别字符数是0, 否则就是对应的长度                unidentified = 0 if sentence[i:j] in dictionary else j - i                # 找最小的dp值                dp[i] = min(dp[i], dp[j] + unidentified)        return dp[0]

[1]

原题链接: