Loading [MathJax]/jax/output/CommonHTML/config.js
首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
MCP广场
社区首页 >专栏 >​LeetCode刷题实战139:单词拆分

​LeetCode刷题实战139:单词拆分

作者头像
程序员小猿
发布于 2021-01-19 03:30:31
发布于 2021-01-19 03:30:31
42500
代码可运行
举报
文章被收录于专栏:程序IT圈程序IT圈
运行总次数:0
代码可运行

今天和大家聊的问题叫做 单词拆分,我们先来看题面:

https://leetcode-cn.com/problems/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. Note: The same word in the dictionary may be reused multiple times in the segmentation. You may assume the dictionary does not contain duplicate words.

题意

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

说明:

拆分时可以重复使用字典中的单词。

你可以假设字典中没有重复的单词。

样例

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
示例 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

解题

这个题可以使用动态规划来解决。动态规划最重要的是状态的定义,好的状态定义能够使解题非常简便。

状态定义:

dp[i]:长度为i的字符串能否拆成wordDict里边的单词组合

状态转移方程:

dp[i] = dp[j] && substr(j, i) in wordDict, (0 <= j < i)

初始状态:

dp[0]=true

以下是C++代码:

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        vector<int> dp(s.size()+1, 0);
        dp[0] = 1;
        unordered_set<string> st(wordDict.begin(), wordDict.end());
        for(int i = 1; i <= s.size(); i++)
        {
            for(int j = 0; j < i; j++)
            {
                auto pos = st.find(s.substr(j, i-j));
                if(dp[j] && pos != st.end())
                {
                    dp[i] = 1;
                    break;
                }
            }
        }
        return dp[s.size()];
    }
};

好了,今天的文章就到这里。

本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2020-12-29,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 程序员小猿 微信公众号,前往查看

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

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

评论
登录后参与评论
暂无评论
推荐阅读
编辑精选文章
换一批
LeetCode 0139 - 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.
Reck Zhang
2021/08/11
2020
LeetCode 139. 单词拆分(DP)
给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict,判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。
Michael阿明
2020/07/13
4260
LeetCode 139. 单词拆分(DP)
动态规划:单词拆分
题目链接:https://leetcode-cn.com/problems/word-break/
代码随想录
2021/02/26
9260
动态规划:单词拆分
​LeetCode刷题实战140:单词拆分 II
https://leetcode-cn.com/problems/word-break-ii/
程序员小猿
2021/01/19
5430
leetcode-139. 单词拆分(记忆化搜索|动态规划)
给定一个非空字符串 s 和一个包含非空单词的列表 wordDict,判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。
全栈程序员站长
2022/09/22
1860
leetcode-139-单词拆分(递归超时,动归解决)
给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict,判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。
chenjx85
2018/09/29
1.2K0
【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
5570
Leetcode 139. 单词拆分
给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict,判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。
zhipingChen
2019/06/19
9750
LeetCode 0140 - Word Break II
Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, add spaces in s to construct a sentence where each word is a valid dictionary word. Return all such possible sentences.
Reck Zhang
2021/08/11
2190
【Leetcode】139.拆分词句
给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict,判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。
Leetcode名企之路
2019/08/16
6350
【Leetcode】139.拆分词句
【常见题型总结】序列 DP 模板题(总结「线性 DP」和「序列 DP」本质区别)
给你一个字符串 s 和一个字符串列表 wordDict 作为字典。请你判断是否可以利用字典中出现的单词拼接出 s 。
宫水三叶的刷题日记
2023/01/03
7800
一天一大 leet(单词拆分)难度:中等 DAY-25
给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict,判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。
前端小书童
2020/09/24
2180
一天一大 leet(单词拆分)难度:中等 DAY-25
Leetcode No.139 单词拆分(动态规划)
给定一个非空字符串 s 和一个包含非空单词的列表 wordDict,判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。
week
2021/11/29
6010
Leetcode No.139 单词拆分(动态规划)
LeetCode 140. 单词拆分 II(DP+回溯)
给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict,在字符串中增加空格来构建一个句子,使得句子中所有的单词都在词典中。返回所有这些可能的句子。
Michael阿明
2020/07/13
8070
LeetCode 140. 单词拆分 II(DP+回溯)
LeetCode 0139. 单词拆分[动态规划详解]
给定一个非空字符串 s 和一个包含非空单词的列表 wordDict,判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。
Yano_nankai
2021/04/12
5590
LeetCode 0139. 单词拆分[动态规划详解]
【每日一题】- leetcode- 139. 单词拆分
为了找到解,我们可以检查字典单词中每一个单词的可能前缀,如果在字典中出现过,那么去掉这个前缀后剩余部分回归调用。
早起的鸟儿有虫吃
2019/09/05
8890
【每日一题】- leetcode- 139. 单词拆分
跟着leedcode刷算法 -- 字符串2
给你一个字符串 s 和一个字符串列表 wordDict 作为字典,判定 s 是否可以由空格拆分为一个或多个在字典中出现的单词。
玖柒的小窝
2021/11/07
3500
跟着leedcode刷算法 -- 字符串2
LeetCode 139. Word Break 动态规划DP Python解法
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. You may assume the dictionary does not contain duplicate words.
大鹅
2021/06/15
6970
LeetCode 139. Word Break 动态规划DP Python解法
【Leetcode】动态规划 刷题训练(八)
若想求以i为结尾的所有子数组的等差数列的个数, 而子数组是连续的,想要构成等差数列,至少使i位置与 i-1和i-2位置构成等差数列
lovevivi
2023/10/17
2580
【Leetcode】动态规划 刷题训练(八)
☆打卡算法☆LeetCode 139. 单词拆分 算法解析
“给定一个字符串s和字符串列表wordDict作为字典,判断是否可以利用字典中出现的单词拼接出s。”
恬静的小魔龙
2022/08/07
5480
☆打卡算法☆LeetCode 139. 单词拆分  算法解析
相关推荐
LeetCode 0139 - Word Break
更多 >
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档