[面试题 17.13][中等][动态规划][前缀树] 恢复空格

题目描述

面试题 17.13. 恢复空格

哦，不！你不小心把一个长篇文章中的空格、标点都删掉了，并且大写也弄成了小写。像句子"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]表示[0, i]子串中, 未识别的字符数. 最后的结果为dp[-1].

考虑状态转移方程, 分为以下情况:

• 字符s[i]无法自身, 或者与之前相连的任何一个子串组成一个单词时, s[i]无法被识别, dp[i]=dp[i-1]+1

• 字符s[i]可以与前面某个子串组成一个单词时, 假设[j,i]代表这个单词

  • 相当于[j,i]子串不会对未识别字符数量做贡献, 相应的dp[i]=dp[j-1]

  • 但需要考虑将[j,i]真的作为一个单词是否合适. 考虑字符串abcde及字典['abcd', 'de'], 对于字符e, 如果将de作为最终的单词, 那么前面的abc就不再是一个词了, 对应的dp[4]=3; 但明显abcd作为一个单词, 只剩一个e, 这种情况下对应的dp[4]=1, 是更合适的

  • 再度观察这个例子, 在i=3时, 我们得到dp[3]=0. 在考虑dp[4]时, 无论如何, 我们都要考虑s[i]不组成单词的情况, 因为这也是一种最优解的情况

考虑以上情况, 在求dp[i]时, 我们首先由dp[i]=dp[i-1]+1得到s[i]不组成单词的情况, 然后从i开始, 向前遍历, 得到所有以s[i]结尾, 且是单词的子串, 根据dp[i]=dp[j-1]得到[j,i]这个单词对应的结果, 然后用min(dp[i], dp[j-1])判别是否应该采纳, 其中初始的dp[1]为dp[i]=dp[i-1]+1. 如果采纳, 更新dp[i], j继续向前寻找可能存在的更长的单词.

但这样寻找单词, 会一直寻找到j=0, 当i较大时, 是比较耗时的. 我们可以结合前缀树进行减值. 说是前缀树, 但在本题中, 是将所有字典中的单词倒过来以构建这棵树. 因为我们查找单词时, 是从后向前逐步覆盖某个单词的. 如果在查找时, 发现某个子串已经不在前缀树中, 就可以停止了. 以此完成剪枝, 提高搜索效率.

整体代码如下, 前缀树Trie树借助嵌套的字典实现.

class Trie:
    def __init__(self):
        self.root = dict()

    def insert(self, word):
        root = self.root
        for c in word[::-1]:
            new_dict = dict()
            cur_dict = root.get(c, new_dict)
            root[c] = cur_dict
            root = cur_dict

    def search(self, word):
        root = self.root
        for c in word[::-1]:
            if c not in root:
                return False
            root = root[c]
        return True


class Solution:
    def respace(self, dictionary: List[str], sentence: str) -> int:
        dic = set(dictionary)
        trie = Trie()
        for word in dictionary:
            trie.insert(word)

        n = len(sentence)
        if n == 0:
            return 0

        dp = [0] * n
        for i in range(n):
            dp[i] = 1 + (dp[i - 1] if i > 0 else 0)
            for j in range(i, -1, -1):
                t_word = sentence[j: i + 1]
                if trie.search(t_word):
                    if t_word in dic:
                        dp[i] = min(dp[i], dp[j - 1] if j > 0 else 0)
                else:
                    break
        return dp[-1]