- 时间： 2020-10-03
- 题目链接：https://leetcode-cn.com/problems/word-break/
- tag：dp
- 题目描述： 给定一个非空字符串 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
法一：动态规划
class Solution:
def wordBreak(self, s: str, wordDict: List[str]) -> bool:
n=len(s)
#使用dp记录单词分词节点。(0,n)为起始位置，(1,n+1)为结束位置
dp=[False]*(n+1)
dp[0]=True
for i in range(n):
for j in range(i+1,n+1):
if (dp[i] and (s[i:j] in wordDict)):
dp[j]=True
return dp[-1]动态规划的改进
class Solution:
def wordBreak(self, s: str, wordDict: List[str]) -> bool:
trues = [0]
#对能进行划分的其实位置进行单独存储，减小了时间和空间复杂度。与法二思想类似。
for j in range(0, len(s)+1):
for i in trues:
if s[i:j] in wordDict:
trues.append(j)
break
return trues[-1]==len(s)法二：记忆回溯
#使用@functools.lru_cache()做缓存，把上一步的结果存下来
class Solution:
def wordBreak(self, s: str, wordDict: List[str]) -> bool:
import functools
@functools.lru_cache(None)
def back_track(s):
if(not s):
return True
res=False
for i in range(1,len(s)+1):
if(s[:i] in wordDict):
res=back_track(s[i:]) or res
return res
return back_track(s)