当前位置: 首页 > news >正文

day39|139.单词拆分 背包问题ending

139.单词拆分

给你一个字符串 s 和一个字符串列表 wordDict 作为字典。请你判断是否可以利用字典中出现的单词拼接出 s 。

注意:不要求字典中出现的单词全部都使用,并且字典中的单词可以重复使用。

示例 1:

输入: s = "leetcode", wordDict = ["leet", "code"]

输出: true

解释: 返回 true 因为 "leetcode" 可以由 "leet" 和 "code" 拼接成。

示例 2:

输入: s = "applepenapple", wordDict = ["apple", "pen"]

输出: true

解释:返回 true
因为 "applepenapple"可以由 "apple" "pen" "apple" 拼接成。

注意,你可以重复使用字典中的单词。

示例 3:

输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]

输出: false

问题分析: 

1、确定dp数组以及下标的含义

dp[j]:拆分字符串的长度为j,dp[j]=true表示可以拆分为一个或多个字典中出现的单词。

2、确定递推公式

完全背包,重复利用物品,且为排列数

字符串为背包,单词为物品,截字符串(j-len,j)看是否是一个单词,并且他的前序子串也是一个或多个单词,也就是判断是否为true

所以递推公式为:

if(j>=len&&dp[j-len]&&word.equals(s.substring(j-len,j)))就为true

3、dp数组初始化

初始化dp[0]=true,否则所有都为false

4、确定遍历顺序

本题要求是排列数,有顺序要求

5、打印dp数组

class Solution {public boolean wordBreak(String s, List<String> wordDict) {boolean[] dp=new boolean[s.length()+1];//有空字符串dp[0]=true;for (int j=1;j<=s.length();j++){for (String word:wordDict){int len=word.length();if (j>=len&&dp[j-len]&&word.equals(s.substring(j-len,j))){dp[j]=true;break;}}}/*  for (int j=1;j<=s.length();j++){System.out.print(dp[j]+" ");}*/return dp[s.length()];}
}

http://www.lryc.cn/news/28004.html

相关文章:

  • Shell脚本编程
  • ChatGPT解答:JavaScript保存当前网页页面图片为pdf文件或者word文件,前端用vue2,给出详细的方案和代码
  • Python基础学习11——文件
  • 外网用户打不开公司的网站?web服务器端口映射到公网
  • 【CS224W】(task9)图神经网络的表示能力(更新中!!)
  • binlog找回误删数据
  • 《程序员面试金典(第6版)》面试题 02.03. 删除中间节点
  • Spring Boot
  • 图论初入门
  • 02-Oracle数据库的启动与关闭
  • 网络营销培训完能达到什么水平?学完能创业吗?
  • 大数据技术之——zeppelin数据清洗
  • Barra模型因子的构建及应用系列五之NonLinear Size因子
  • C++ 常用命令行开发工具(Linux)
  • java基础学习 day47(抽象类,抽象方法)
  • Java代码弱点与修复之——Open redirect(开放重定向)
  • Go 指针
  • shardingsphere5.1.1分表分库yaml配置 自定义策略
  • “探索未来:VR全景直播技术引领新媒体时代”
  • Spring Cloud(微服务)学习篇(六)
  • MATLAB-Scatter3-三维散点图投影至XYZ三个平面
  • Unity/C#------委托与事件(一篇文章彻底搞懂...)
  • 别再为 Jenkins 安装烦恼,Docker 帮你轻松解决
  • 汇编语言程序设计(一)
  • 【uni-app教程】四、UniAPP 路由配置及页面跳转
  • ROS从入门到精通系列(二十八)-- ROS控制器图形化界面开发
  • Submodule命令:android如何将自己项目中的某个Module作为gitlab中第三方公共库
  • MySQL索引事务
  • ISO27001信息安全管理体系认证
  • Linux应用GUI开发C++ 之gtkmm4(1)