首页 > 其他分享 >139. 单词拆分(leetcode)

139. 单词拆分(leetcode)

时间:2024-09-04 19:14:45浏览次数:10  
标签:String int boolean 拆分 wordDict new 139 true leetcode

https://leetcode.cn/problems/word-break/description/

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        // 思路较为巧妙,和传统背包定义不同
        // f[i]表示长度为i的字符串能否被wordDict里的单词凑成
        // 状态转义方程也和传统背包不同,需要从题意出发来进行推导
        // 若有j<=i,且 s[j~i]这个子串是 存在于wordDict中的,且f[j]=true
        // 意味着可以由f[j]推导出f[i],即f[i]= f[j] && check(s[j~i])
        // 那么答案就是f[s.length()]
        // 由于求的不是组合而是排列,因此需要先背包再物品
        // 初值:为了方便进行推导,定义f[0]表示空串,为true,f[1]才表示凑成第一个字符的选法,这里f[0]不会影响答案,只是便于计算推导
        // 相当于把s当做背包,s的子串当做物品,判断wrodDict中是否存在,存在即可以凑出来s
        Map<String,Boolean> map = new HashMap<>();
        for(String str:wordDict)map.put(str,true);
        int N = 310;
        boolean[] f=new boolean[N];
        f[0]=true;
        for(int i=1;i<=s.length();i++)
        {
            for(int j=0;j<i;j++) // 子串
            {
                String substr=s.substring(j,i);
                Boolean flag=map.get(substr);
                if(f[j]==true && flag!=null && flag==true)
                    f[i]=true;
            }
        }
        return f[s.length()];
        
    }
}
class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        // 另一种f定义
        // 这类集合中选元素,且是排列问题的,统一可以当做爬楼梯模型来做
        // 如,f[i]表示能否爬到第i阶楼梯,或者说能否构字符串s
        // 以最后一步从哪爬取的来划分子集,且能爬上来的一定是wordDict的谋个元素
        // 即求f[i]的话,是从小于i的楼层爬上来的
        // 能够一步爬上来意味着j~i之间这个子串存在于wordDict中
        // f[i]=f[j] && j~i这个子串存在于wordDict中
        // f[0]表示第0层楼,一定能爬上,为true
        
        Map<String,Boolean> map = new HashMap<>();
        for(String str:wordDict)map.put(str,true);
        int N = 310;
        boolean[] f=new boolean[N];
        f[0]=true;
        for(int i=1;i<=s.length();i++)
        {
            for(int j=0;j<i;j++) // 子串
            {
                String substr=s.substring(j,i);
                Boolean flag=map.get(substr);
                if(f[j]==true && flag!=null && flag==true)
                    f[i]=true;
            }
        }
        return f[s.length()];
        
    }
}

 

标签:String,int,boolean,拆分,wordDict,new,139,true,leetcode
From: https://www.cnblogs.com/lxl-233/p/18397208

相关文章

  • LeetCode刷题—数组
    一:数组操作1、数组:在连续的内存空间当中;存储一组相同类型的元素2、元素和索引:数组的索引下标从0开始3、数组的访问和数组的搜索(1)数组的访问a=[1,2,3]a[1]=2#数组的访问;通过下标索引进行访问(2)数组的搜索a=[1,2,3]foriina:print(i)4、数组的四种方法访问0(1)......
  • 2024.9.4 leetcode169 多数元素 (C++)
    题面https://leetcode.cn/problems/majority-element/description/ 解答一开始想得比较暴力,直接把对应数字当数组下标,遇到对应数字,数组++,但不知道怎么处理-10^9~10^9的数据大小,后来想了一个办法,那就是先排序,再求连续的个数,个数大于n/2的时候,return结果。太久没接触C++语法、......
  • 【数据结构和算法实践-树-LeetCode100-判断是否是相同的树】
    数据结构和算法实践-树-LeetCode100-判断是否是相同的树题目MyThought代码示例JAVA-8题目给你两棵二叉树的根节点p和q,编写一个函数来检验这两棵树是否相同。如果两个树在结构上相同,并且节点具有相同的值,则认为它们是相同的。示例输入:p=[1,2,3],q=[1,2......
  • 【数据结构和算法实践-链表-LeetCode23-合并K个有序数组】
    合并K个有序数组题目MyThought代码示例JAVA-8题目合并K个有序数组MyThought一、将ListNode放入PriorityQueue中1.1、设置PriorityQueue的比较器规则1.2、将ListNode[]放入priorityQueue二、再将数据依次弹出放到ListNode中代码示例JAVA-8publicListNod......
  • Stable Diffusion【XL Lora】推荐!AI助力服装设计,让服装拆分设计就是这么高效!
    今天给大家介绍一个服装饰品分类背景的基于SDXL的Lora模型:分类背景XUER。该模型是由作者(B站绪儿已成精)炼制,非常适合饰品服装分类背景。绪儿大佬其实推出了很多非常棒的模型,比如之前非常受大家喜欢的敦煌飞天、超梦幻场景等模型。下面我们来实际体验一下,看使用这个模型出来的图片......
  • 代码随想录算法训练营|Day06 LeetCode 242.有效的字母异位词,349.两个数组的交集,202.快
    理论知识哈希表是根据关键码的值而直接进行访问的数据结构,一般用来快速判断一个元素是否出现在集合里映射——哈希函数哈希碰撞线性探测法拉链法常用的哈希结构数组set(集合)map(映射)242.有效的字母异位词242.有效的字母异位词-力扣(LeetCode)classSolution{......
  • 算法练习题10:leetcode76最小覆盖子串-滑动窗口
    目录题目题目描述约束条件解决思路代码getOrDefault(c,0) 方法方法签名参数返回值示例getOrDefault 与 get 的主要区别Integer 题目题目描述给定两个字符串s和t,请你在字符串s中找到包含t中所有字符的最小子串。要求:        如果 s ......
  • Leetcode面试经典150题-239.滑动窗口最大值
    解法都在代码里,不懂就留言或者私信官方定级hard难度,其实是medium,确实字节考过classSolution{publicint[]maxSlidingWindow(int[]nums,intk){if(nums.length==1){returnnewint[]{nums[0]};}/**我们要返回的是一个......
  • Leetcode面试经典150题-54.螺旋矩阵
      解法都在代码里,不懂就留言或者私信这个题可能和算法关联不大,coding技巧为上classSolution{publicList<Integer>spiralOrder(int[][]matrix){/**先定义结果集*/List<Integer>ans=newArrayList<>();/**当前位置从(0,0)开始*/......
  • 【前端面试】leetcode树javascript
    写一个树//定义二叉树节点functionTreeNode(val,left,right){this.val=(val===undefined?0:val)this.left=(left===undefined?null:left)this.right=(right===undefined?null:right)}//示例使用constroot=newTr......