力扣labuladong一刷day63天单词拆分

这篇具有很好参考价值的文章主要介绍了力扣labuladong一刷day63天单词拆分。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

力扣labuladong一刷day63天单词拆分

一、139. 单词拆分

题目链接:https://leetcode.cn/problems/word-break/description/
思路:s是否能被拆分成字典中的单词,单词数量是不限的,故是完全背包问题,不限数量的单词是否能组成字符串s,可以看的出来,并不是要求你长度相等就可以,还得有一定的顺序才能排列成字符串s,故本题还是一个排列问题。for循环的遍历顺序,背包在外物品在内是排列,物品在外背包在内是组合。
定义dp[i]表示,s[0, i]可以被字典元素拼出来,那么如果s[j, i]是字典元素,且dp[j]是true,就说明dp[i]可以被拼出。
故递推公式为 if([j, i] 这个区间的子串出现在字典里 && dp[j]是true) 那么 dp[i] = true。

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        Set<String> set = new HashSet<>(wordDict);
        boolean[] dp = new boolean[s.length()+1];
        dp[0] = true;
        for (int i = 1; i < dp.length; i++) {
            for (int j = 0; j < i && !dp[i]; j++) {
                if (set.contains(s.substring(j, i)) && dp[j]) {
                    dp[i] = true;
                }
            }
        }
        return dp[s.length()];
    }
}

另外采用回溯的方法也可以做,不过要把遍历改为子问题,下面这个就是改造成分解子问题,当前片段存在字典中,只要后续的都可以拼接说明字符串s可以被拼接。

if (set.contains(s.substring(index, i+1))) {
	 boolean subProblem = dp(s,i+1);
}
class Solution {
    Set<String> set;
    int[] visited;
    public boolean wordBreak(String s, List<String> wordDict) {
        set = new HashSet<>(wordDict);
        visited = new int[s.length()];
        Arrays.fill(visited, -1);
        return dp(s, 0);
    }

    boolean dp(String s, int index) {
        if (index == s.length()) {
            return true;
        }
        if (visited[index] != -1) {
            return visited[index] != 0;
        }
        for (int i = index; i < s.length(); i++) {
            if (set.contains(s.substring(index, i+1))) {
                boolean subProblem = dp(s,i+1);
                if (subProblem) {
                    visited[i] = 1;
                    return true;
                }
            }
        }
        visited[index] = 0;
        return false;
    }
}

二、140. 单词拆分 II

题目链接:https://leetcode.cn/problems/word-break-ii/description/
思路:处理字符串的排列组合还是回溯更好处理一些,本题采用回溯的方法进行处理,很简单的回溯模板。文章来源地址https://www.toymoban.com/news/detail-811038.html

class Solution {
    LinkedList<String> track;
    List<String> res;
    List<String> wordDict;
    public List<String> wordBreak(String s, List<String> wordDict) {
        track = new LinkedList<>();
        res = new LinkedList<>();
        this.wordDict = wordDict;
        dp(s, 0);
        return res;
    }
    void dp(String s, int index) {
        if (index == s.length()) {
            res.add(String.join(" ", track));
            return;
        }
        for (String word : wordDict) {
            int len = word.length();
            if (index + len <= s.length() && s.substring(index, index + len).equals(word)) {
                track.addLast(word);
                dp(s, index+len);
                track.removeLast();
            }
        }
    }
}

到了这里,关于力扣labuladong一刷day63天单词拆分的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 力扣labuladong——一刷day18

    提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档 双指针技巧处理数组问题,常用的是左右指针,和快慢指针

    2024年02月06日
    浏览(44)
  • 力扣labuladong一刷day59天动态规划

    力扣labuladong一刷day59天动态规划 一、509. 斐波那契数 题目链接:https://leetcode.cn/problems/fibonacci-number/description/ 思路:这是非常典型的一道题,下面是优化过的代码,a,b就是dp数组,因为每计算一个值,需要前两个值,这个a,b就是用来记录前两个值,避免重复计算,递推公式便

    2024年01月21日
    浏览(48)
  • 力扣labuladong一刷day39天最近公共祖先问题

    力扣labuladong一刷day39天最近公共祖先问题 一、236. 二叉树的最近公共祖先 题目链接:https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/ 思路:寻找最近公共祖先,在前序的位置判断,如果找到一个就返回,然后在后序的位置收尾,即左右子树都遍历过了,如果都找到的话

    2024年02月04日
    浏览(37)
  • 力扣labuladong一刷day40天计算完全二叉树节点数

    力扣labuladong一刷day40天计算完全二叉树节点数 一、222. 完全二叉树的节点个数 题目链接:https://leetcode.cn/problems/count-complete-tree-nodes/ 思路:计算完全二叉树直接全遍历的话很浪费时间,但是可以利用完全二叉树的特性来解题, 每到一个节点我们就计算它的left = node.left深度,

    2024年02月04日
    浏览(41)
  • 算法 DAY45 动态规划07 70. 爬楼梯 322. 零钱兑换 279. 完全平方数 139. 单词拆分 多重背包

    和377. 组合总和 Ⅳ (opens new window)基本就是一道题了。 本题代码不长,题目也很普通,但稍稍一进阶就可以考察完全背包 动态规划五部曲 1、确定dp[j]的含义 dp[j] 凑成 j 的最少硬币的个数 2、确定递推公式 比如想凑成3, 如果手里有1,那么最小个数就是dp[2]+1 如果手里有2,那

    2024年02月02日
    浏览(59)
  • 力扣 | 139. 单词拆分

    主要是要注意组合的顺序是任意的!所以就要先选择目标字串,再选择wordDict

    2024年01月22日
    浏览(35)
  • 力扣 139. 单词拆分

    给你一个字符串 s 和一个字符串列表 word_dict 作为字典。请你判断是否可以利用字典中出现的单词拼接出 s 。 注意 :不要求字典中出现的单词全部都使用,并且字典中的单词可以重复使用。 通过 回溯法 进行 暴力 求解,时间复杂度 O ( n × 2 n ) O(n times 2^n) O ( n × 2 n ) ,空间

    2024年02月03日
    浏览(34)
  • 力扣 -- 139. 单词拆分

     题目链接:139. 单词拆分 - 力扣(LeetCode) 下面是用动态规划的思想解决这道题的过程,相信各位小伙伴都能看懂并且掌握这道经典的动规题目滴。   以上就是用动态规划的思想分析这道题目的整个过程啦,你学会了吗?如果以上题解对你有所帮助,那么就点亮一下小心心

    2024年02月14日
    浏览(43)
  • 力扣:139. 单词拆分

    动态规划: 1.先声明dp数组的含义为下标i表示的是在s变量中i前面的字符串是否在wordDict变量中存在,初始化dp【0】来进行后面dp数组的递推。同时要判断截取的值是否在wirdDict中是否存在,还要判断dp【j】的下标的j前面的字符串是否也在wirdDict中,如果都符合条件就给dp【i】

    2024年02月20日
    浏览(38)
  • 力扣--动态规划139.单词的拆分

    一开始,我有一个很简单的想法。 思路分析: 使用动态规划,初始化一个长度为 len + 1 的 dp 数组,其中 dp[i] 表示字符串 s 的前 i 个字符是否可以被成功拆分。 使用 unordered_set 存储 wordDict 中的单词,以提高查找效率。 外层循环遍历字符串 s ,内层循环遍历 wordDict 中的单词

    2024年02月20日
    浏览(39)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包