Keshawn_lu's Blog

Leetcode 面试题 17.13. 恢复空格

动态规划
字数统计: 542阅读时长: 2 min
2020/07/09 Share

题目简介：

哦，不！你不小心把一个长篇文章中的空格、标点都删掉了，并且大写也弄成了小写。像句子I reset the computer. It still didn’t boot!已经变成了"iresetthecomputeritstilldidntboot"。在处理标点符号和大小写之前，你得先把它断成词语。当然了，你有一本厚厚的词典dictionary，不过，有些词没在词典里。假设文章用sentence表示，设计一个算法，把文章断开，要求未识别的字符最少，返回未识别的字符数。

示例：

1
2
3
4
5
输入：
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]为sentence[0...i]的未匹配字符个数。

首先sentence = " " + sentence，处理边界问题。

定义一个哈希表，将字典中的单词存入。

将每个dp[i]初始化值为dp[i - 1] + 1(即先默认sentence[i]为不匹配字符)，然后j从1遍历到i(sentence[0]为空格，单词表中可能有一个字符的单词)，若sentence[j ... i]为单词表中的单词，则这部分是匹配成功的，所以dp[i] = min(dp[i], dp[j - 1])(保留最小值)。

最后返回dp[sentence.size() - 1]即可。

tip:

  • 看题解用字典树效率更高，先留个坑以后来做。现在用的方法时间复杂度O(n^2)，用时感人…

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
public:
    int respace(vector<string>& dictionary, string sentence) {

        unordered_map<string, int> map;

        sentence = " " + sentence;
        vector<int> dp(sentence.size(), 0);   //以i结尾的未匹配字符个数

        for(int i = 0; i < dictionary.size(); i++)
            map[dictionary[i]]++;

        for(int i = 1; i < sentence.size(); i++){

            dp[i] = dp[i - 1] + 1;

            for(int j = 1; j <= i; j++){

                //j...i的字符串为单词
                if(map.count(sentence.substr(j, i - j + 1))){   

                    //j...i已匹配成功。
                    dp[i] = min(dp[i], dp[j - 1]);  
                }
            }
        }

        return dp[sentence.size() - 1];
    }
};
CATALOG
  1. 1. 题目简介：
  2. 2. 思路：
  3. 3. 代码如下：
Total : 424
2023
2022
2021
2020
2019
动态规划 树 深度优先搜索 哈希表 数组 深度优先遍历 单调栈 字符串 双指针 栈 贪心 图 模拟 广度优先搜索 回溯 滑动窗口 二分查找 广度优先遍历 记忆化搜索 数学 链表 前缀和 双向链表 优先队列 拓扑排序 KMP 堆 字典树 递归 并查集 矩阵 位运算 双端队列 吴恩达团队NLP 吴恩达深度学习 线性表
杂谈 算法相关 PAT 2019推理小说阅读计划 NLP 深度学习 大三课程学习 大四课程学习 浙工商OJ 牛客网