专栏首页Michael阿明学习之路程序员面试金典 - 面试题 17.13. 恢复空格(DP+Trie树)

程序员面试金典 - 面试题 17.13. 恢复空格(DP+Trie树)

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个未识别字符。(jess tim)

提示:
0 <= len(sentence) <= 1000
dictionary中总字符数不超过 150000。
你可以认为dictionary和sentence中只包含小写字母。

来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/re-space-lcci 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

2. 解题

2.1 动态规划

  • dp[i] 表示包含 i 字符结尾的字符串 最少的未识别字符数,初始为 i+1(全部未识别)
  • 将 [ 0, i ] 区间切分,[ 0, j-1 ],[ j, i ] ,遍历所有的 j (j <= i)
  • 如果字典包含字符串 [ j, i ],dp[i]=min⁡(dp[i],dp[j−1])dp[i] = \min(dp[i], dp[j-1])dp[i]=min(dp[i],dp[j−1])
  • 如果字典不包含字符串 [ j, i ],dp[i]=min⁡(dp[i],dp[j−1]+i−j+1)dp[i] = \min(dp[i], dp[j-1]+i-j+1)dp[i]=min(dp[i],dp[j−1]+i−j+1)
  • 一旦 dp[i] == 0,可以终止内层循环
class Solution {
public:
    int respace(vector<string>& dictionary, string sentence) {
        if(sentence.empty())
            return 0;
    	int i, j, n = sentence.size();
        unordered_set<string> s;
        vector<int> dp(n,INT_MAX);
    	for(auto& d : dictionary)
    		s.insert(d);
        for(i = 0; i < n; ++i)
        {
            dp[i] = i+1;
            if(s.count(sentence.substr(0,i+1)))
            {
                dp[i] = 0;
                continue;
            }
            for(j = i; j > 0; --j)
            {
                if(s.count(sentence.substr(j,i-j+1)))
                    dp[i] = min(dp[i], dp[j-1]);
                else
                    dp[i] = min(dp[i], dp[j-1]+i-j+1);
                if(dp[i]==0)
                    break;
            }
        }
        return dp[n-1];
    }
};

1156 ms 446.1 MB

2.2 Trie树

  • 在上面的思路下,将字典字符串反向插入trie树
  • 内层循环可以改为向前在trie树中查找存在的字符串最大长度,一旦不存在某个字符就不必再往前遍历了,因为肯定不存在,可以提高效率。
class trie
{
public:
	trie* cur;
	trie* next[26] = {NULL};
	bool isEnd = false;

	void insert(string& s)
	{
		cur = this;
		for(int i = s.size()-1; i >= 0; --i)//反向插入
		{
			if(cur->next[s[i]-'a'] == NULL)
			{
				cur->next[s[i]-'a'] = new trie();
			}
			cur = cur->next[s[i]-'a'];
		}
		cur->isEnd = true;
	}
};

class Solution {
public:
    int respace(vector<string>& dictionary, string sentence) {
    	if(sentence.empty())
    		return 0;
    	int i, j, n = sentence.size();
        unordered_set<string> s;
    	trie *t = new trie(), *cur;
    	for(auto& d : dictionary)
    		t->insert(d);//字典插入trie树
        vector<int> dp(n,INT_MAX);
        for(i = 0; i < n; ++i)
        {
            dp[i] = i+1;
            cur = t;
            for(j = i; j >= 0; --j)//从i处向前在trie树中查找单词
            {	
                if(cur->next[sentence[j]-'a'])//下一个字符存在
                {
                	if(cur->next[sentence[j]-'a']->isEnd)//且是结束位置
                    {
                    	if(j > 0)
                    		dp[i] = min(dp[i], dp[j-1]);
                    	else
                    		dp[i] = 0;
                    }
                    else//不是结束位置,不匹配
                    {
                    	if(j > 0)
                    		dp[i] = min(dp[i], dp[j-1]+i-j+1);
                    	else
                    		dp[i] = min(dp[i], i-j+1);
                    }
                }
                else//下一个字符不存在,可以结束了
                {
                    if(j > 0)
                    	dp[i] = min(dp[i], dp[j-1]+i-j+1);
                    else
                        dp[i] = min(dp[i], i-j+1);
                    break;
                }
                if(dp[i]==0)	break;
                cur = cur->next[sentence[j]-'a'];
            }
        }
        return dp[n-1];
    }
};

120 ms 153.8 MB

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • LeetCode 279. 完全平方数(DP)

    给定正整数 n,找到若干个完全平方数(比如 1, 4, 9, 16, …)使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。

    Michael阿明
  • LeetCode 357. 计算各个位数不同的数字个数(DP)

    给定一个非负整数 n,计算各位数字都不同的数字 x 的个数,其中 0 ≤ x < 10n。

    Michael阿明
  • LeetCode 801. 使序列递增的最小交换次数(动态规划)

    我们可以交换 A[i] 和 B[i] 的元素。注意这两个元素在各自的序列中应该处于相同的位置。

    Michael阿明
  • of baskets he can fill completely!Help Phoenix determine the maximum number

    Problem Description Phoenix is picking berries in his backyard. There are n shr...

    w4979的博客
  • LeetCode 70. Climbing Stairs

    ShenduCC
  • 告别动态规划,连刷40道动规算法题,我总结了动规的套路

    动态规划难吗?说实话,我觉得很难,特别是对于初学者来说,我当时入门动态规划的时候,是看 0-1 背包问题,当时真的是一脸懵逼。后来,我遇到动态规划的题,看的懂答...

    帅地
  • 打卡群2刷题总结1013——不同的二叉搜索树

    https://leetcode-cn.com/problems/unique-binary-search-trees/

    木又AI帮
  • 动态规划该如何优化?我总结了这些套路,以后优化就是分分钟

    前两天写一篇长达 8000 字的关于动态规划的文章告别动态规划,连刷40道动规算法题,我总结了动规的套路

    帅地
  • 打卡群刷题总结0928——整数拆分

    链接:https://leetcode-cn.com/problems/integer-break

    木又AI帮
  • 一天一大 leet(三角形最小路径和)难度:中等-Day20200715

    dp[i] = dp[0]xdp[i-1] + (dp[1]xdp[i-2]) + ... + (dp[i-2]xdp[1]) + dp[i-1]*dp[0]

    前端小书童

扫码关注云+社区

领取腾讯云代金券