LintCode 单词切分题目分析

题目

给出一个字符串s和一个词典,判断字符串s是否可以被空格切分成一个或多个出现在字典中的单词。

样例 给出 s = "lintcode" dict = ["lint","code"] 返回 true 因为"lintcode"可以被空格切分成"lint code"

分析

这道题算动态规划里比较复杂的,对时间复杂度要求也比较高。笔者没加最大长度的判断语句,就直接Time Limit Exceeded了。 下面来分析具体的算法思路: dp[i]:表示前i个字符能不能被完整的切分,要么为true,要么为false. 假设判断到了第i个字符,我们还要在内部用一个循环判断,从1到i 个字符,在哪个地方可以被切分,这个循环变量用j表示,那么dp[i]为true的条件是,dp[i-j]为true,且后面s.subString(i-j,i)这个字符串要在dict里面出现,只要满足这个条件,那么dp[i]才能为true。 这样的思路是不错的,但是结果却超时了,说明算法还有可以优化的地方,那么在哪里呢? 当我们在j循环的时候,显然需要小于dict里面最大长度

public class Solution {
    /**
     * @param s: A string s
     * @param dict: A dictionary of words dict
     */
    public boolean wordBreak(String s, Set<String> dict) {
        if (s == null || s.length() == 0) {
            return true;
        }

        int minLength = getMinLength(dict);
        int maxLength = getMaxLength(dict);
        //前i个字符能不能切分
        boolean[] canSegment = new boolean[s.length() + 1];

        canSegment[0] = true;
        for (int i = 1; i <= s.length(); i++) {
            canSegment[i] = false;
            for (int j = 0;
                     j <=i-minLength  && j<=i;
                     j++) {
                         
                if(j < i-maxLength)
                    continue;
                
                //如果前半部分不可切分,那不用看后半部分,直接进入下一个循环判断
                if (!canSegment[j]) {
                    continue;
                }
                //前半部分可分割,取出后半部分的字符串,进行遍历判断
                String word = s.substring(j, i);
                if (dict.contains(word)) {
                    //如果存在,则表明此时是可以分割的,直接跳出第二层循环
                    canSegment[i] = true;
                    break;
                }
            }
        }

        return canSegment[s.length()];
    }
    
    private int getMinLength(Set<String> dict) {
        int maxlenth = 0;
        for(String word : dict) {
            maxlenth = Math.min(maxlenth, word.length());
        }
        return maxlenth;
    }
    
    private int getMaxLength(Set<String> dict) {
        int maxlenth = 0;
        for(String word : dict) {
            maxlenth = Math.max(maxlenth, word.length());
        }
        return maxlenth;
    }
}

Paste_Image.png

我们需要换一个想法,就是在j循环的时候倒过来

public boolean wordBreak(String s, Set<String> dict) {
        if (s == null || s.length() == 0) {
            return true;
        }

        int maxLength = getMaxLength(dict);
        //前i个字符能不能切分
        boolean[] canSegment = new boolean[s.length() + 1];

        canSegment[0] = true;
        for (int i = 1; i <= s.length(); i++) {
            canSegment[i] = false;
            for (int lastWordLength = 1;
                     lastWordLength <= maxLength && lastWordLength <= i;
                     lastWordLength++) {
                //如果前半部分不可切分,那不用看后半部分,直接进入下一个循环判断
                if (!canSegment[i - lastWordLength]) {
                    continue;
                }
                //前半部分可分割,取出后半部分的字符串,进行遍历判断
                String word = s.substring(i - lastWordLength, i);
                if (dict.contains(word)) {
                    //如果存在,则表明此时是可以分割的,直接跳出第二层循环
                    canSegment[i] = true;
                    break;
                }
            }
        }

        return canSegment[s.length()];
    }
    
    private int getMaxLength(Set<String> dict) {
        int maxlenth = 0;
        for(String word : dict) {
            maxlenth = Math.max(maxlenth, word.length());
        }
        return maxlenth;
    }

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏闵开慧

java概念1

public static void main(String[] args) {//其中[]也可以写在args后面,args也可以随便写成其他字母,例如asd...

36111
来自专栏iOS122-移动混合开发研究院

【读书笔记】A Swift Tour

素材:A Swift Tour 推荐下载Playground:Download Playground objc 自己较为熟悉,想熟悉下风头正劲的 swift。就...

3618
来自专栏绿巨人专栏

[Java] 设计模式: Code Shape - 管理你的代码结构

982
来自专栏服务端技术杂谈

Java编码规范

命名 类名使用UpperCamelCase风格。 领域模型相关命名:DO / DTO / VO / DAO等。 方法名,参数名,成员变量,局部变量都统一使用lo...

3334
来自专栏Java开发者杂谈

java如何获取一个对象的大小

When---什么时候需要知道对象的内存大小 在内存足够用的情况下我们是不需要考虑java中一个对象所占内存大小的。但当一个系统的内存有限,或者某块程序代码允许...

1.4K7
来自专栏成长道路

java常用对象

boolean b=Pattern.matches("(86)*0*1\\d{10}",mobile);//大陆手机号码的匹配 日期类 Date date =...

2240
来自专栏Ryan Miao

Java String.split()用法小结

在java.lang包中有String.split()方法,返回是一个数组 我在应用中用到一些,给大家总结一下,仅供大家参考: 1、如果用“.”作为分隔的话,必...

34711
来自专栏逸鹏说道

Python3 与 C# 基础语法对比(List、Tuple、Dict专栏)

Python3 与 C# 基础语法对比(基础知识场):https://www.cnblogs.com/dotnetcrazy/p/9102030.html

943
来自专栏极乐技术社区

使用ES6新特性开发微信小程序(1)

ECMAScript 6(简称ES6)是JavaScript语言的最新标准。因为当前版本的ES6是在2015年发布的,所以又称ECMAScript 2015。 ...

2285
来自专栏老九学堂

十七个C语言新手编程时常犯的错误及解决方式

编译程序把a和A认为是两个不同的变量名,而显示出错信息。C认为大写字母和小写字母是两个不同的字符。习惯上,符号常量名用大写,变量名用小写表示,以增加可读性。

1614

扫码关注云+社区

领取腾讯云代金券