文档章节

leetcode面试题 17.13(恢复空格)--Java语言实现

 拓拔北海
发布于 07/09 18:09
字数 936
阅读 38
收藏 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个未识别字符。
提示:

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

 

解:

1、动态规划

未识别的字符数=所有字符数(字符长长度)-已识别的字符数。

因为每一步的结果与上一步的结果相关,且与之后的结果无关,符合动态规划的典型特征。我们使用一个一维的dp数组保存每一步的结果。

从前往后使用一个变量i顺序遍历字符串,遍历字符串的过程中,dp[i]或者等于dp[i-1],或者因为子串出现了与dictionary中字典的匹配(遍历字符串使用变量j),为dp[i-dictionary[j].length]+dictionary.length。选择这2者中的较大者,作为dp[i]。注意这里为了确保下标有效,需要保证i>=dictionary.length。

时间复杂度:O(M^2*N),其中M是字典字符串数组的长度,N是sentence字符串的长度(substring的复杂度是O(N),外面2层for循环)

空间复杂度:O(N)

public int respace(String[] dictionary, String sentence) {
    int N = sentence.length();
    int M = dictionary.length;
    int dp[] = new int[N+1];
    for(int i=1;i<=N;i++){
        dp[i]=dp[i-1];
        for(int j=0;j<M;j++){
            int dicLen = dictionary[j].length();
            if(i<dicLen) continue;
            if(sentence.substring(i-dicLen,i).equals(dictionary[j]))
                dp[i] = Math.max(dp[i],dp[i-dicLen]+dicLen);
        }
    }
    return N-dp[N];
}

 

2、动态规划+线段树

这是一个非常适合本题的数据结构。核心思想是将dictionary数组中的字符串,按反向顺序遍历字符,然后加入到线段树中。这样从线段树的根节点遍历树的时候,就相当于与字典做匹配。具体可以参考官方给出的题解。这个方法整体复杂度较高,难度在于对于线段树的插入、遍历需要熟悉,并且需要和动态规划结合。

时间复杂度:O(∣dictionary∣+n
空间复杂度:O(∣dictionary∣∗S+n)

class Solution {
    public int respace(String[] dictionary, String sentence) {
        int n = sentence.length();

        Trie root = new Trie();
        for (String word : dictionary) {
            root.insert(word);
        }

        int[] dp = new int[n + 1];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;
        for (int i = 1; i <= n; ++i) {
            dp[i] = dp[i - 1] + 1;

            Trie curPos = root;
            for (int j = i; j >= 1; --j) {
                int t = sentence.charAt(j - 1) - 'a';
                if (curPos.next[t] == null) {
                    break;
                } else if (curPos.next[t].isEnd) {
                    dp[i] = Math.min(dp[i], dp[j - 1]);
                }
                if (dp[i] == 0) {
                    break;
                }
                curPos = curPos.next[t];
            }
        }
        return dp[n];
    }
}

class Trie {
    public Trie[] next;
    public boolean isEnd;

    public Trie() {
        next = new Trie[26];
        isEnd = false;
    }

    public void insert(String s) {
        Trie curPos = this;

        for (int i = s.length() - 1; i >= 0; --i) {
            int t = s.charAt(i) - 'a';
            if (curPos.next[t] == null) {
                curPos.next[t] = new Trie();
            }
            curPos = curPos.next[t];
        }
        curPos.isEnd = true;
    }
}

 

3、动态规划+字符串哈希

参考官方题解,与方法2类似,但是能达到更好的空间复杂度。

粉丝 0
博文 208
码字总数 113305
作品 0
私信 提问
加载中
请先登录后再评论。
Netty那点事(三)Channel与Pipeline

Channel是理解和使用Netty的核心。Channel的涉及内容较多,这里我使用由浅入深的介绍方法。在这篇文章中,我们主要介绍Channel部分中Pipeline实现机制。为了避免枯燥,借用一下《盗梦空间》的...

黄亿华
2013/11/24
2W
22
用vertx实现高吞吐量的站点计数器

工具:vertx,redis,mongodb,log4j 源代码地址:https://github.com/jianglibo/visitrank 先看架构图: 如果你不熟悉vertx,请先google一下。我这里将vertx当作一个容器,上面所有的圆圈要...

jianglibo
2014/04/03
3.9K
3
SQLServer实现split分割字符串到列

网上已有人实现sqlserver的split函数可将字符串分割成行,但是我们习惯了split返回数组或者列表,因此这里对其做一些改动,最终实现也许不尽如意,但是也能解决一些问题。 先贴上某大牛写的s...

cwalet
2014/05/21
9.6K
0
Swift百万线程攻破单例(Singleton)模式

一、不安全的单例实现 在上一篇文章我们给出了单例的设计模式,直接给出了线程安全的实现方法。单例的实现有多种方法,如下面: class SwiftSingleton { } 这段代码的实现,在shared中进行条...

一叶博客
2014/06/20
3.3K
16
程序猿媛一:Android滑动翻页+区域点击事件

滑动翻页+区域点击事件 ViewPager+GrideView 声明:博文为原创,文章内容为,效果展示,思路阐述,及代码片段。文尾附注源码获取途径。 转载请保留原文出处“http://my.oschina.net/gluoyer...

花佟林雨月
2013/11/09
4.1K
1

没有更多内容

加载失败,请刷新页面

加载更多

Java中使用OpenSSL生成的RSA公私钥进行数据加解密

当前使用的是Linux系统,已经按装使用OpenSSL软件包, 一、使用OpenSSL来生成私钥和公钥 1、执行命令openssl version -a 验证机器上已经安装openssl openssl version -a 运行结果: 2、生成...

osc_1psr53ow
2分钟前
0
0
计算机毕业设计之springboot+vue.js点餐小程序 点餐系统

功能 后台: 1. 超级管理员(具有该系统所有权限)登录 查看系统所有管理员 操作:可新添加管理员并分配系统已有角色; 可对已有管理员进行信息编辑; 可对除超管外的其他管理员账号禁用/启用...

osc_x4ot1joy
3分钟前
0
0
MATLAB数学建模

链接:https://pan.baidu.com/s/1WA2ltwyMZuKeo7OC9XAIvw 提取码:tmy2 记录matlab参加建模比赛时所用的书籍,避免忘记 链接:https://pan.baidu.com/s/1WA2ltwyMZuKeo7OC9XAIvw 提取码:tmy...

osc_oa6qrgun
4分钟前
0
0
Python中可以使用静态类变量吗? - Are static class variables possible in Python?

问题: Is it possible to have static class variables or methods in Python? Python中是否可以有静态类变量或方法? What syntax is required to do this? 为此需要什么语法? 解决方案:...

技术盛宴
35分钟前
17
0
如何在Android中以像素为单位获取屏幕尺寸 - How to get screen dimensions as pixels in Android

问题: I created some custom elements, and I want to programmatically place them to the upper right corner ( n pixels from the top edge and m pixels from the right edge). 我创建......

javail
今天
7
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部