面试题恢复空格分析

熊孩纸 阅读:260 2020-10-21 17:05:46 评论:0

哦,不!你不小心把一个长篇文章中的空格、标点都删掉了,并且大写也弄成了小写。像句子"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个未识别字符。

解:这个题挺难得 记录下最简单的动态规划写法

分析:拿到题目,先想贪心能不能做,显然不行。比如给定字符串:abcdef,字典:["abcd", "ab", "def"],贪心匹配是 abcd ef,有2个字符未匹配。显然有更优匹配策略: ab c def ,只有 1 个字符未匹配。所以这题需要用动态规划来解决(怎么思考一个题目可不可以用 dp 来解决,先假设 dp 表达含义,再想转移方程,很多时候自然而然就出来了)。

1、状态定义:
dp[i] 表示字符串的前 i 个字符的最少未匹配数。

2、状态转移:
假设当前我们已经考虑完了前 i 个字符了,对于前 i + 1 个字符对应的最少未匹配数:

第 i + 1 个字符未匹配,则 dp[i + 1] = dp[i] + 1,即不匹配数加 1;
遍历前 i 个字符,若以其中某一个下标 idx 为开头、以第 i + 1 个字符为结尾的字符串正好在词典里,则 dp[i] = min(dp[i], dp[idx]) 更新 dp[i]。

class Solution { 
public: 
        int respace(vector<string>& dictionary, string sentence) { 
        set<string> set_dict(dictionary.begin(),dictionary.end()); 
        int n=sentence.size(); 
        vector<int> dp(n+1,0); 
 
        for(int i=1;i<=n;i++) 
        { 
            dp[i]=dp[i-1]+1; 
            for(int index=0;index<i;index++) 
            { 
                if(set_dict.find(sentence.substr(index,i-index))!=set_dict.end()) 
                { 
                    dp[i]=min(dp[i],dp[index]); 
                } 
            } 
        } 
        return dp[n]; 
    } 
};

但是会超时。。。

声明

1.本站遵循行业规范,任何转载的稿件都会明确标注作者和来源;2.本站的原创文章,请转载时务必注明文章作者和来源,不尊重原创的行为我们将追究责任;3.作者投稿可能会经我们编辑修改或补充。

发表评论
搜索
排行榜
关注我们

可以免费观看全网VIP电影的公众号