夜间模式暗黑模式
字体
阴影
滤镜
圆角
主题色
面试题 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中只包含小写字母。 

 Related Topics 字典树 数组 哈希表 字符串 动态规划 哈希函数 滚动哈希 

代码:

    public int respace(String[] dictionary, String sentence) {
        Set<String> dictionarySet = new HashSet<>(Arrays.asList(dictionary));
        int length = sentence.length();
        int[] dp = new int[length + 1];
        for (int size = 1; size <= length; size++) {
            dp[size] = dp[size - 1] + 1;
            for (int idx = 0; idx < size; idx++) {
                if (dictionarySet.contains(sentence.substring(idx, size))) {
                    dp[size] = Math.min(dp[idx], dp[size]);
                }
            }
        }
        return dp[length];
    }

求最短路径的题目:

暂无评论

发送评论 编辑评论


				
上一篇
下一篇