Leetcode 139. 单词拆分
题目描述
给定一个非空字符串 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
递归解法
以 wordBreak(s, wordDict) 作为判断字符串 s 可否拆分为 wordDict 的函数。则对于字符串 s 和下标 i，若 s[:i+1] 在 wordDict 中，如果 wordBreak(s[i+1:], wordDict) 返回 True，则表示字符串 s 可被拆分为 wordDict。
class Solution:
def wordBreak(self, s: str, wordDict: List[str]) -> bool:
if not s:
return True
for i in range(len(s)):
if s[:i+1] in wordDict and self.wordBreak(s[i+1:],wordDict):
return True
return False递归运算可能存在大量的重复计算，当字符串较大时可能会超时。
递归+存储中间值解法
以 wordMatch 存储字符串对应函数值。
class Solution:
def wordBreak(self, s: str, wordDict: List[str]) -> bool:
wordMatch,wordSet=dict(),set(wordDict)
def breakCyc(s):
if not s:
return True
for i in range(len(s)):
if s[:i+1] in wordSet:
flag=wordMatch.get(s[i+1:],-1)
if flag==-1:
flag=breakCyc(s[i+1:])
wordMatch[s[i+1:]]=flag
if flag:
return True
return False
return breakCyc(s)动态规划解法
以列表 arr 记录字符串 s 的每个可拆分前缀的下标，则从上一个前缀继续拓展遍历时，若当前的子字符串可拆分，则必然由前面的某一个可拆分前缀和 wordDict 中某个单词组成。
class Solution:
def wordBreak(self, s: str, wordDict: List[str]) -> bool:
arr,wordSet=[0],set(wordDict)
for i in range(len(s)):
for j in arr[::-1]:
if s[j:i+1] in wordSet:
arr.append(i+1)
break
return arr[-1]==len(s)本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2019.06.19 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读