小型网站开发,惠州做网站乐云seo轻松上线,网站的建设和维护的钱,上海企业倒闭难度#xff1a; 中等通过率#xff1a; 33.7%题目链接#xff1a;. - 力扣#xff08;LeetCode#xff09;
题目描述
给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict#xff0c;判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。
说明#…难度 中等通过率 33.7%题目链接. - 力扣LeetCode
题目描述
给定一个非空字符串 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. 广度优先搜索
整个字符串是由多个单词拼接而成的这些单词的拼接组合构成了一颗巨大的树。如果有一条路径上的单词可以构成该字符串则说明有解。但是暴力搜索这个树其时间复杂度为 O(n^n)。
基于广度优先的搜索方法可以大幅度减少时间复杂度。其思想是在字典中寻找字符串的前缀然后移除前缀继续寻找前缀。直到最后字符串为空时认为字典里的单词可以构成该字符串。
下面的代码中从下标 0 开始寻找前缀字符串然后将结尾下标入队列下一次取出该值作为新的起始下标。
class Solution:def wordBreak(self, s: str, wordDict) - bool:queue [0]words set(wordDict)while queue:start queue.pop(0)if start len(s):return Truefor end in range(start1, len(s)1):if s[start:end] in words:queue.append(end)return False但是上面这种方法依然超时了动态规划能够得到更低的时间复杂度。
解法 2. 动态规划
对于字符串 s如果 s[:i] 和 s[i:] 均可以由字典中的单词组成那么整个字符串 s 也就可以由字典中单词组成。
用 dp[i] 表示 s[:i] 是否可由字典中单词组成。
class Solution:def wordBreak(self, s: str, wordDict) - bool:dp [False] * (len(s) 1)dp[0] Truewords set(wordDict)for i in range(1, len(s)1):for j in range(0, i):if dp[j] and s[j:i] in words:dp[i] Truebreakreturn dp[-1]
