# LeetCode: 139. 单词拆分¶

## 1、题目描述¶

• 拆分时可以重复使用字典中的单词。
• 你可以假设字典中没有重复的单词。

输入: s = "leetcode", wordDict = ["leet", "code"]



输入: s = "applepenapple", wordDict = ["apple", "pen"]

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


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



## 2、解题思路¶

​ 这道题也可以用深度优先搜索，如果整个单词都被搜索完毕，返回真，否则返回假

​ 因为在数组中找到单词比较慢，我们直接使用字典来做，先将wordDict转换为字典

​ 很遗憾，用递归超出了时间限制。。。

class Solution(object):
def wordBreak(self, s, wordDict):
"""
:type s: str
:type wordDict: List[str]
:rtype: bool
"""
word_dict = {}
for i in wordDict:
word_dict[i] = 1
return self.dfs(s, word_dict)

def dfs(self, s, word_dict):
if s == "":
return True

result = False
for i in range(1, len(s) + 1):
if s[:i] in word_dict:
result = result or self.dfs(s[i:], word_dict)

return result


​ 再来分析一下这个题目，实际上，我们发现，假如前面i-1个字符能够用字典中的单词匹配，那么前i个能不能呢

​ 假如 0<=j <= i-1, 我们发现j的时候能够匹配，并且s[j:i+1]也在字典中，那么当前的肯定能够匹配成功

​ 为了匹配第一个字母，dp的长度是len(s)+1

​ 举个例子，

s = "leetcode", wordDict = ["leet", "code"]

dp = [True, False, False, False, False, False, False, False, False]

dp = [True, False, False, False, False, False, False, False, False]

dp[0] and "le"  False
dp[1] and "e"   False

dp[0] and "lee" False
dp[1] and "ee"  False
dp[2] and "e"   False


class Solution(object):
def wordBreak(self, s, wordDict):
"""
:type s: str
:type wordDict: List[str]
:rtype: bool
"""
word_dict = {}
for i in wordDict:
word_dict[i] = 1

length = len(s)

dp = [False] * (length + 1)

dp[0] = True

for i in range(1, length + 1):
temp = False
for j in range(i):
temp = dp[j] and s[j:i] in word_dict
if temp:
break
dp[i] = temp

return dp[len(s)]