当前位置:首页 » 《随便一记》 » 正文

每日写题分享--单词拆分/动态规划/剪枝_Wangling_blog的博客

14 人参与  2022年04月07日 18:14  分类 : 《随便一记》  评论

点击全文阅读


题目描述:

给你一个字符串 s 和一个字符串列表 wordDict 作为字典,判定 s 是否可以由空格拆分为一个或多个在字典中出现的单词。

说明:拆分时可以重复使用字典中的单词。


题目链接戳此

思路:首先将字典放进set里面,方便判断字典中是否包含某个单词,并求出字典中最长单词的长度(下面解析中有解释)。再根据题意,如果一个字符串合法(即拆分后的单词全都在字典里能查询到),那么这个字符串去掉一个单词也是合法的,由此能得到动态转移方程。

具体实现根据下面代码解析:如果在单词长度为 i 时,j 从 i - 1开始向前探索,一直探索到0位置时,如果满足 s的(i - j)不分的字符串存在于字符串,并且dp[0]为true,就说明这一段存在于字典里,这是定义dp[i] = true,假设此时的i位置为k。下一次探索的时候j从新的i-1位置开始,此时就不用探索到0位置才能返回true了,因为只要j从i位置开始走,到k的位置,满足[k,j]这一段存在字典中就可以了,if条件里dp[k]在上一次已经被置为true了,符合条件语句的判断。

刚才描述的代码还是可以优化的,也就是j 从 i - 1开始向前探索,一直探索到0位置,如果中间发现i-j大于字典中出现的单词中最大的长度,那么字典就不可能包含这个单词,所以可以在if语句多加上这个条件。这也就是剪枝思想。

代码实现如下:

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        int len = s.length();
        int max = 0;
        Set<String> set = new HashSet<>();
        for (String str : wordDict) {
            if (!set.contains(str)) {
                set.add(str);
                max = Math.max(max,str.length());
            }
        }        
        boolean[] dp = new boolean[len + 1];

        //dp[0]本身没有意义,题目中给的s是非空的,这里只是方便解题给定的初始值。
        dp[0] = true;
        for (int i = 1; i <= s.length();i++) {

        //i - j <= max作用:剪枝。如果探索的长度大于字典里最长单词的长度,就没必要继续探索了。
            for (int j = i - 1;j >= 0 && i - j <= max ;j--) {
                if (dp[j] && set.contains(s.substring(j,i))) {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[len];
    }
}


点击全文阅读


本文链接:http://m.zhangshiyu.com/post/37547.html

字典  单词  字符串  
<< 上一篇 下一篇 >>

  • 评论(0)
  • 赞助本站

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。

最新文章

  • 我在回忆里万劫不复精彩节选(秦见鹿谢梵声)_我在回忆里万劫不复精彩节选
  • 迟迟白日晚全书+后续(路星延宋栀年)_(迟迟白日晚全书+后续)迟迟白日晚全书+后续列表_笔趣阁(路星延宋栀年)
  • 往梦难复温+全书+后续(沈淮霆宋思予)列表_往梦难复温(沈淮霆宋思予)往梦难复温+全书+后续在线
  • 兰因絮果,爱恨全如玉碎全书+后续+结局(谢长乐肖风行)列表_兰因絮果,爱恨全如玉碎(谢长乐肖风行)兰因絮果,爱恨全如玉碎全书+后续+结局在线
  • 从此星辰远,归途似海深人气节选(璃月龙影)全书免费_(璃月龙影)从此星辰远,归途似海深人气节选后续(璃月龙影)
  • 全文你来时风起云涌番外+(陆翊夏天瑜赵歆)列表_全文你来时风起云涌番外+
  • 人面兽小说精彩节选免费试读_小浩言语小蕊爆款小说高能章节试读
  • 你来时风起云涌免费(陆翊夏天瑜赵歆)
  • 四海八荒苦封喉,君心似毒酒结局+番外+后续看点十足(洛虞玄澈)_四海八荒苦封喉,君心似毒酒结局+番外+后续看点十足(洛虞玄澈)洛虞玄澈免费列表_笔趣阁(洛虞玄澈)
  • 「错宠假千金,全京城权贵暴虐侯府」章节多结局预体验‌_沈轻漾楚珩完结版免费在线阅读
  • 画地为牢(池念谢宴清)_画地为牢(池念谢宴清)
  • 完结文往梦难复温列表_完结文往梦难复温(沈淮霆宋思予)

    关于我们 | 我要投稿 | 免责申明

    Copyright © 2020-2022 ZhangShiYu.com Rights Reserved.豫ICP备2022013469号-1