# LeetCode: 140. 单词拆分 II¶

## 1、题目描述¶

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

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

[
"cats and dog",
"cat sand dog"
]


输入:
s = "pineapplepenapple"
wordDict = ["apple", "pen", "applepen", "pine", "pineapple"]

[
"pine apple pen apple",
"pineapple pen apple",
"pine applepen apple"
]



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

[]


## 2、解题思路¶

• 动态规划加上回溯
• 首先借助动态规划进行划分，判断当前字符串能否被分割，并且获得了相应可分隔位置的标记
dp = [False] * (N + 1)
dp[0] = True

for i in range(1, N + 1):
for j in range(i):
if dp[j] and s[j:i] in word_mapping:
dp[i] = True
break

• 然后我们判断最后一个是否是True，如果是，就表示能够被分割
• 因此，从后面向前找单词进行回溯
• 如果找到的单词落到的点是False，就表示不可分割点，回溯，重新新寻找

class Solution:
def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:
from collections import deque

N = len(s)
word_mapping = set(wordDict)
dp = [False] * (N + 1)
dp[0] = True

for i in range(1, N + 1):
for j in range(i):
if dp[j] and s[j:i] in word_mapping:
dp[i] = True
break

if not dp[N]:
return []
res = []

temp = deque()

def dfs(pos):
if pos == 0:
res.append(list(temp))
return

if not dp[pos]:
return

for p in range(pos - 1, -1, -1):
if s[p:pos] in word_mapping:
temp.appendleft(s[p:pos])
dfs(p)
temp.popleft()

dfs(N)
return [" ".join(x) for x in res]