恢复空格

难度: Medium

哦，不！你不小心把一个长篇文章中的空格、标点都删掉了，并且大写也弄成了小写。像句子"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中只包含小写字母。

Submission

运行时间: 68 ms

内存: 16.5 MB

class Solution:
    def respace(self, dictionary: List[str], sentence: str) -> int:
        dictionary = [x for x in dictionary if x in sentence]
        dp = [float('inf')] * (len(sentence)+1)
        dp[0] = 0
        for i in range(len(sentence)+1):
            dp[i] = min(dp[i],dp[i-1]+1)
            for x in dictionary:
                j = i + len(x)
                if sentence[i:j] == x:
                    dp[j] = min(dp[j],dp[i])
        return dp[-1]

Explain

此题解采用了动态规划的方法。首先，将词典中在句子中出现的词筛选出来，以减少后续的计算量。然后，定义一个动态规划数组dp，其中dp[i]表示句子中前i个字符中未识别的字符数量的最小值。初始时，dp[0]=0，表示空字符串中没有未识别的字符。接着，遍历句子中的每个字符，对于每个位置i，首先将dp[i]更新为dp[i-1]+1，因为句子中的第i个字符可能是未识别的，然后遍历筛选后的词典，检查以当前位置为结尾的子字符串是否是词典中的单词，如果是，则尝试更新dp[j]（j是单词结束的位置），使得dp[j]=min(dp[j], dp[i])，这表示如果以i结尾的子字符串是一个词典中的单词，那么前j个字符中未识别的字符数量可以不包括这个单词。最后，返回dp数组的最后一个元素，即为整个句子中未识别的字符数量的最小值。

时间复杂度: O(nmk)

空间复杂度: O(n)

class Solution:
    def respace(self, dictionary: List[str], sentence: str) -> int:
        dictionary = [x for x in dictionary if x in sentence]  # 筛选出在句子中出现的词
        dp = [float('inf')] * (len(sentence)+1)  # 初始化动态规划数组
        dp[0] = 0  # 空字符串中没有未识别的字符
        for i in range(len(sentence)+1):
            dp[i] = min(dp[i],dp[i-1]+1)  # 更新当前位置的未识别字符数量
            for x in dictionary:
                j = i + len(x)
                if sentence[i:j] == x:
                    dp[j] = min(dp[j],dp[i])  # 如果当前子字符串是词典中的单词，更新dp[j]
        return dp[-1]  # 返回整个句子中未识别的字符数量的最小值

Explore

在动态规划数组`dp`中，`dp[i]`表示句子中前i个字符中未识别的字符数量的最小值。初始化`dp[0]=0`因为空字符串中没有未识别的字符。其他位置初始值设置为`float('inf')`是为了在后续的动态规划过程中能够使用`min`函数来正确地比较并选择最小值。如果使用0或具体的大数，可能会导致无法正确更新最小值，因为这些初始值可能会被错误地识别为最小的未识别字符数量，尤其是在字符串的某些部分实际上可以完全由词典中的单词覆盖时。`float('inf')`作为一个足够大的数，保证了任何实际的字符数都会比它小，从而在比较时能被正确更新。

这种筛选方法的确可能导致一些必要词汇被遗漏。例如，如果词典中的某个词没有在句子中单独出现，而是作为其他更长词汇的一部分出现，那么这种筛选就会将其排除，尽管这个词是必要的。这种情况在词汇嵌套或重叠时尤为明显，如词典中的'abc'和'ab'，而句子中只有'abc'。如果只检查完全匹配，'ab'将不会被包括在筛选后的词典中，但实际上它可能对解决问题非常重要。因此，这种筛选虽然可以减少计算量，但也可能影响算法的准确性和效率。

此方法在每次循环中都要对子字符串进行判断，这可能导致效率较低，特别是当句子和词典中的单词较长时。更高效的字符串匹配方法包括使用哈希表或字典树（Trie）。例如，可以先将所有词典中的单词存储在一个字典树中，然后遍历句子，使用字典树来检查以每个位置开始可能形成的所有单词。这种方法可以显著提高匹配的速度，因为字典树能够在O(m)时间内完成检查（m是单词的长度），并且可以同时处理多个潜在匹配项。