首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
MCP广场
社区首页 >专栏 >139. 单词拆分

139. 单词拆分

作者头像
张伦聪zhangluncong
发布于 2022-10-26 10:25:06
发布于 2022-10-26 10:25:06
30200
代码可运行
举报
运行总次数:0
代码可运行

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

说明:

拆分时可以重复使用字典中的单词。 你可以假设字典中没有重复的单词。 示例 1:

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
输入: s = "leetcode", wordDict = ["leet", "code"]
输出: true
解释: 返回 true 因为 "leetcode" 可以被拆分成 "leet code"

示例 2:

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
输入: s = "applepenapple", wordDict = ["apple", "pen"]
输出: true
解释: 返回 true 因为 "applepenapple" 可以被拆分成 "apple pen apple"。
     注意你可以重复使用字典中的单词。

示例 3:

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
输出: false

解:

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        int length = s.length();
        //dp[i]表示
        boolean[] dp = new boolean[length + 1];
        dp[0] = true;

        for (int i = 1; i <= length; i++) {
            for (int j = 0; j < i; j++) {
                String sub = s.substring(j, i);
                if (dp[j] && wordDict.contains(sub)) {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[length];
    }
}
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2018-09-11,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
暂无评论
推荐阅读
编辑精选文章
换一批
【Leetcode】139.拆分词句
给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict,判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。
Leetcode名企之路
2019/08/16
6380
【Leetcode】139.拆分词句
LeetCode 139. 单词拆分(DP)
给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict,判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。
Michael阿明
2020/07/13
4280
LeetCode 139. 单词拆分(DP)
LeetCode 0139. 单词拆分[动态规划详解]
给定一个非空字符串 s 和一个包含非空单词的列表 wordDict,判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。
Yano_nankai
2021/04/12
5630
LeetCode 0139. 单词拆分[动态规划详解]
LeetCode - #139 单词拆分
文章链接:https://cloud.tencent.com/developer/article/2469020
Swift社区
2024/11/22
2840
LeetCode - #139 单词拆分
Leetcode No.139 单词拆分(动态规划)
给定一个非空字符串 s 和一个包含非空单词的列表 wordDict,判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。
week
2021/11/29
6080
Leetcode No.139 单词拆分(动态规划)
​LeetCode刷题实战139:单词拆分
https://leetcode-cn.com/problems/word-break/
程序员小猿
2021/01/19
4260
一天一大 leet(单词拆分)难度:中等 DAY-25
给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict,判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。
前端小书童
2020/09/24
2200
一天一大 leet(单词拆分)难度:中等 DAY-25
Leetcode 139. 单词拆分
给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict,判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。
zhipingChen
2019/06/19
9780
139. 单词拆分
题目 /** * 给定一个非空字符串 s 和一个包含非空单词的列表 wordDict,判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。 * 说明: * 拆分时可以重复使用字典中的单词。 * 你可以假设字典中没有重复的单词。 * * 示例 1: * 输入: s = "leetcode", wordDict = ["leet", "code"] * 输出: true * 解释: 返回 true 因为 "le
名字是乱打的
2021/12/23
4740
跟着leedcode刷算法 -- 字符串2
给你一个字符串 s 和一个字符串列表 wordDict 作为字典,判定 s 是否可以由空格拆分为一个或多个在字典中出现的单词。
玖柒的小窝
2021/11/07
3560
跟着leedcode刷算法 -- 字符串2
【每日一题】- leetcode- 139. 单词拆分
为了找到解,我们可以检查字典单词中每一个单词的可能前缀,如果在字典中出现过,那么去掉这个前缀后剩余部分回归调用。
早起的鸟儿有虫吃
2019/09/05
8900
【每日一题】- leetcode- 139. 单词拆分
leetcode-139-单词拆分(递归超时,动归解决)
给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict,判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。
chenjx85
2018/09/29
1.2K0
leetcode-139. 单词拆分(记忆化搜索|动态规划)
给定一个非空字符串 s 和一个包含非空单词的列表 wordDict,判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。
全栈程序员站长
2022/09/22
1860
单词拆分\\
给你一个字符串 s 和一个字符串列表 wordDict 作为字典。请你判断是否可以利用字典中出现的单词拼接出 s 。
狼啸风云
2023/12/23
3150
单词拆分\\
☆打卡算法☆LeetCode 139. 单词拆分 算法解析
“给定一个字符串s和字符串列表wordDict作为字典,判断是否可以利用字典中出现的单词拼接出s。”
恬静的小魔龙
2022/08/07
5520
☆打卡算法☆LeetCode 139. 单词拆分  算法解析
【常见题型总结】序列 DP 模板题(总结「线性 DP」和「序列 DP」本质区别)
给你一个字符串 s 和一个字符串列表 wordDict 作为字典。请你判断是否可以利用字典中出现的单词拼接出 s 。
宫水三叶的刷题日记
2023/01/03
7890
dp算法 力扣978、力扣139、力扣467
更正式地来说,当 arr 的子数组 A[i], A[i+1], ..., A[j] 满足仅满足下列条件时,我们称其为湍流子数组:
用户10788736
2023/10/16
2260
dp算法 力扣978、力扣139、力扣467
动态规划:单词拆分
题目链接:https://leetcode-cn.com/problems/word-break/
代码随想录
2021/02/26
9270
动态规划:单词拆分
140. 单词拆分 II
给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict,在字符串中增加空格来构建一个句子,使得句子中所有的单词都在词典中。返回所有这些可能的句子。
张伦聪zhangluncong
2022/10/26
2150
【DP】139. Word Break
Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, determine if s can be segmented into a space-separated sequence of one or more dictionary words.
echobingo
2019/06/05
5590
相关推荐
【Leetcode】139.拆分词句
更多 >
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档