题目：
给定一个非空字符串 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
分析
题意：将s进行分割，分割后的多个字符串是否都可以在wordDict中找到。
第一种想法：
将s进行分割，然后将分割的字符串去匹配是否在字典里。但是这种做法有个难点，如何分割，分割成几段？
先从第一个字符开始分割，分割后将左边的字符拿去判断是否在字典里？如果在，就把右边的字符串进行相同的操作（递归）；如果不在，就从第二个位置开始分割，依次进行。
于是写下下面的代码：
class Solution:
def wordBreak(self, s: str, wordDict: List[str]) -> bool:
total = len(s)
if total <= 0:
return False
for firstIndex in range(total):
leftStr = s[:firstIndex+1]
if leftStr in wordDict:
if len(leftStr) == total :
return True
rightStr = s[firstIndex+1:]
isRightOk = self.wordBreak(rightStr,wordDict)
if isRightOk:
return True
return False
但是当测试用例为：
"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab"
["a","aa","aaa","aaaa","aaaaa","aaaaaa","aaaaaaa","aaaaaaaa","aaaaaaaaa","aaaaaaaaaa"]
超出了时间限制。因为递归程度太深了，导致超出限制。
第二种想法：
既然上面以切割s不行，那就遍历数组，遇到第一个匹配的，就切割一下字符串s，拿着余下部分再去看看字典里有没有。
比如 startTestabc 字典里是[start,right,te,test,ab] ,遍历数组，发现第一个元素start是字符串s的开头，就切割字符串拿到后面的部分Testabc，再判断数组里的元素是否有开头能匹配Testabc。
代码如下：
class Solution:
def wordBreak(self, s: str, wordDict: List[str]) -> bool:
for subStr in wordDict:
if s.startswith(subStr):
nextStr = s[len(subStr):]
if len(nextStr) <= 0:
return True
isMatch = self.wordBreak(nextStr,wordDict)
if isMatch:
return True
return False
时间复杂度仍然很高。和上面的解法其实一样，同样超出了时间限制。
超出限制的原因都是因为递归深度过高，那怎么解决呢？记忆法，记录下不符合条件的情况，减少不必要的判断.
最终代码如下：
第一种修改后的代码
class Solution:
def p_wordBreak(self,s:str,wordDict:List[str],mapSet) -> bool:
total = len(s)
if total <= 0:
return False
if s in mapSet :
return False
for firstIndex in range(total):
leftStr = s[:firstIndex+1]
if leftStr in wordDict:
if len(leftStr) == total :
return True
rightStr = s[firstIndex+1:]
isRightOk = self.p_wordBreak(rightStr,wordDict,mapSet)
if isRightOk:
return True
mapSet.add(s)
return False
def wordBreak(self, s: str, wordDict: List[str]) -> bool:
return self.p_wordBreak(s,wordDict,set())
第二种修改后的代码
class Solution:
def p_wordBreak(self,s:str,wordDict:List[str],mapSet) -> bool:
if s in mapSet:
return False
for subStr in wordDict:
if s.startswith(subStr):
nextStr = s[len(subStr):]
if len(nextStr) <= 0:
return True
isMatch = self.p_wordBreak(nextStr,wordDict,mapSet)
if isMatch:
return True
mapSet.add(s)
return False
def wordBreak(self, s: str, wordDict: List[str]) -> bool:
return self.p_wordBreak(s,wordDict,set())
leetCode解答通过：
image.png
网友评论