面试题 17.13. 复原空格

题目起源：力扣（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]。
• 可用字典树进行优化。（不太纯熟，暂留空）

欢送关注

公众号【书所集录】