Loading [MathJax]/jax/output/CommonHTML/config.js
首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
MCP广场
社区首页 >专栏 >跟着leedcode刷算法 -- 字符串2

跟着leedcode刷算法 -- 字符串2

作者头像
玖柒的小窝
修改于 2021-11-08 01:16:31
修改于 2021-11-08 01:16:31
34500
代码可运行
举报
文章被收录于专栏:各类技术文章~各类技术文章~
运行总次数:0
代码可运行

题三:

单词拆分

给你一个字符串 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 <= s.length <= 300

1 <= wordDict.length <= 1000

1 <= wordDict[i].length <= 20

s 和 wordDict[i] 仅有小写英文字母组成

wordDict 中的所有字符串 互不相同

相关标签

  • 字典树
  • 记忆化搜索
  • 哈希表
  • 字符串
  • 动态规划

动态规划思路:

  • 对s进行拆分,s[0..j-1]和s[j:i]两个部分,其中j = 0..i-1
  • 判断以上两个部分是否在wordDict中,而s[0..j-1]可以用dp[j]替代

代码:

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        dp = [True]+[False for _ in range(len(s))]
        for i in range(1,len(s)+1):
            for j in range(i):
                if dp[j] and s[j:i] in wordDict:
                    dp[i] = True
                    break 
        return dp[len(s)]
复制代码

运行结果:

第四题:

单词拆分 II

给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict,在字符串中增加空格来构建一个句子,使得句子中所有的单词都在词典中。返回所有这些可能的句子。

说明:

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

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

示例 2:

输入:

s = "pineapplepenapple"

wordDict = ["apple", "pen", "applepen", "pine", "pineapple"]

输出:

[ "pine apple pen apple", "pineapple pen apple", "pine applepen apple" ]

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

示例 3:

输入:

s = "catsandog"

wordDict = ["cats", "dog", "sand", "and", "cat"]

输出: []

相关标签

  • 字典树
  • 记忆化搜索
  • 哈希表
  • 字符串
  • 动态规划
  • 回溯

这个题和之前的分割回文串思路很像都是dfs算法

话不多说,直接上代码

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:        
        def dfs(n):
            if n == len(s):
                res.append(" ".join(list(items)))
                return
            
            for i in range(n,len(s)):
                if s[n:i + 1] in wordDict:
                    items.append(s[n:i + 1])  
                    dfs(i + 1)
                    items.pop()
        
        res = []
        items = []
        dfs(0)
        return res
复制代码

执行结果:

对比一下分割回文算法:

很多题都很相似,大家可以灵活运用一下

本文系转载,前往查看

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

本文系转载,前往查看

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

评论
登录后参与评论
暂无评论
推荐阅读
编辑精选文章
换一批
​LeetCode刷题实战139:单词拆分
https://leetcode-cn.com/problems/word-break/
程序员小猿
2021/01/19
4180
​LeetCode刷题实战140:单词拆分 II
https://leetcode-cn.com/problems/word-break-ii/
程序员小猿
2021/01/19
5370
英语单词记忆法拆分2000个_usually拆分记忆
给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict,在字符串中增加空格来构建一个句子,使得句子中所有的单词都在词典中。返回所有这些可能的句子。
全栈程序员站长
2022/09/22
3480
【常见题型总结】序列 DP 模板题(总结「线性 DP」和「序列 DP」本质区别)
给你一个字符串 s 和一个字符串列表 wordDict 作为字典。请你判断是否可以利用字典中出现的单词拼接出 s 。
宫水三叶的刷题日记
2023/01/03
7730
leetcode-139. 单词拆分(记忆化搜索|动态规划)
给定一个非空字符串 s 和一个包含非空单词的列表 wordDict,判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。
全栈程序员站长
2022/09/22
1820
一天一大 leet(单词拆分)难度:中等 DAY-25
给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict,判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。
前端小书童
2020/09/24
2140
一天一大 leet(单词拆分)难度:中等 DAY-25
leetcode-139-单词拆分(递归超时,动归解决)
给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict,判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。
chenjx85
2018/09/29
1.2K0
Leetcode 139. 单词拆分
给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict,判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。
zhipingChen
2019/06/19
9720
LeetCode 139. 单词拆分(DP)
给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict,判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。
Michael阿明
2020/07/13
4190
LeetCode 139. 单词拆分(DP)
140. 单词拆分 II
给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict,在字符串中增加空格来构建一个句子,使得句子中所有的单词都在词典中。返回所有这些可能的句子。
张伦聪zhangluncong
2022/10/26
2080
LeetCode 0140. 单词拆分 II[动态规划详解]
给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict,在字符串中增加空格来构建一个句子,使得句子中所有的单词都在词典中。返回所有这些可能的句子。
Yano_nankai
2021/04/12
4660
LeetCode 0140. 单词拆分 II[动态规划详解]
力扣每日一刷(2023.9.14)
进阶:如果给定的数组中含有负数会发生什么?问题会产生何种变化?如果允许负数出现,需要向题目中添加哪些限制条件?
用户11097514
2024/05/31
1330
动态规划:单词拆分
题目链接:https://leetcode-cn.com/problems/word-break/
代码随想录
2021/02/26
9170
动态规划:单词拆分
【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
5500
【一天一大 lee】单词拆分 II (难度:困难) - Day20201101
给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict,在字符串中增加空格来构建一个句子,使得句子中所有的单词都在词典中。返回所有这些可能的句子。
前端小书童
2020/11/03
4880
【一天一大 lee】单词拆分 II (难度:困难) - Day20201101
LeetCode 0139. 单词拆分[动态规划详解]
给定一个非空字符串 s 和一个包含非空单词的列表 wordDict,判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。
Yano_nankai
2021/04/12
5520
LeetCode 0139. 单词拆分[动态规划详解]
【Leetcode】139.拆分词句
给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict,判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。
Leetcode名企之路
2019/08/16
6290
【Leetcode】139.拆分词句
LeetCode 140. 单词拆分 II(DP+回溯)
给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict,在字符串中增加空格来构建一个句子,使得句子中所有的单词都在词典中。返回所有这些可能的句子。
Michael阿明
2020/07/13
8000
LeetCode 140. 单词拆分 II(DP+回溯)
Leetcode No.140 单词拆分 II(DFS)
给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict,在字符串中增加空格来构建一个句子,使得句子中所有的单词都在词典中。返回所有这些可能的句子。 说明: 分隔时可以重复使用字典中的单词。 你可以假设字典中没有重复的单词。
week
2022/01/06
6320
算法刷题-Excel表列序号、单词拆分 II、排序链表
给你一个字符串 columnTitle ,表示 Excel 表格中的列名称。返回该列名称对应的列序号。
共饮一杯无
2023/03/09
6770
算法刷题-Excel表列序号、单词拆分 II、排序链表
相关推荐
​LeetCode刷题实战139:单词拆分
更多 >
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档
本文部分代码块支持一键运行,欢迎体验
本文部分代码块支持一键运行,欢迎体验