139. 单词拆分
2023-04-18 16:12:02 时间
题目
/**
* 给定一个非空字符串 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"。
* 注意你可以重复使用字典中的单词。
*/
思路:
- 1.这是一个完全背包问题,本题可以转换为是否可以用现有单词拼成该字符串
- 2.我们可以把问题逐步拆分,比如一个applepenapple,我们可以先看applepen可不可以组成,applepen可以组成applepenapple就等于applepen和apple,以此递推
代码:
public boolean wordBreak(String s, List<String> wordDict) {
Set<String> words = new HashSet<>(wordDict);
boolean[] hasCheck = new boolean[s.length() + 1];
//hasCheck[i]表示:字符串的前i个字符是否可以由背包中的单词组成
hasCheck[0] = true;
// 如果确定hasCheck[j] 是true,且 [j, i] 这个区间的子串出现在字典里,那么dphasChecki]一定是true。(j < i )。
// 所以递推公式是 if([j, i] 这个区间的子串出现在字典里 && hasCheck[j]是true) 那么 dp[i] = true。
for (int i = 1; i <= s.length(); i++) {
//倒着遍历,考虑到单词长度可能远小于target长度,倒着遍历效率更高
for (int j = i - 1; j >= 0; j--) {
if (!hasCheck[j]) {
continue;
}
if (hasCheck[j] && words.contains(s.substring(j, i ))) {
hasCheck[i] = true;
break;
}
}
}
return hasCheck[s.length()];
}
相关文章
- 为什么开发人员离开谷歌
- 又一巨头宣布入局AIGC,一口气开源数个模型,还道出了它的变现之道
- 《Science》公布年度十大突破,AIGC、AI for science赢麻了
- 杀猪盘被AI大模型套路,倒贴520块钱,骗子破大防
- 关于运维,阿里云、字节、华科的专家如是说
- 行业 SaaS 微服务稳定性保障实战
- 提前在开发阶段暴露代码问题,携程Alchemy代码质量平台
- Twitter 抛弃开源
- 编辑部已成羊村,这几天幸亏有ChatGPT(doge)
- 首次不依赖生成模型,一句话让AI修图!
- 德勤发布2023年六大技术趋势:“信任”贯穿其中
- 神经渲染与AI生成框架结合,五倍提升游戏速度,英伟达是这样做的
- ChatGPT与搜索引擎合体,谷歌都不香了,LeCun转发
- 2022年各国程序员编程水平排行榜出炉,排名第一的国家没听说过
- 达摩院开源低成本大规模分类框架FFC
- 谷歌计划合并地图和Waze团队以削减成本,称不打算裁员
- 地址标准化服务AI深度学习模型推理优化实践
- ChatGPT国产平替出现了:APP商店就能下载,还可给AI加人设,背后公司刚成立3个月
- ChatGPT 用户已破百万,是玩具还是生产力?
- 拼写错误、代码中少打了个空格:摧毁了 DDoS 僵尸网络