[LeetCode]140. 单词拆分 II(Word Break II)

题目描述

给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict,在字符串中增加空格来构建一个句子,使得句子中所有的单词都在词典中。返回所有这些可能的句子。

说明:

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

输入:
s = “catsanddog”
wordDict = [“cat”, “cats”, “and”, “sand”, “dog”]
输出:
[
“cats and dog”,
“cat sand dog”
]

示例 2:

输入:
s = “pineapplepenapple”
wordDict = [“apple”, “pen”, “applepen”, “pine”, “pineapple”]
输出:
[
“pine apple pen apple”,
“pineapple pen apple”,
“pine applepen apple”
]
解释: 注意你可以重复使用字典中的单词。

示例 3:

输入:
s = “catsandog”
wordDict = [“cats”, “dog”, “sand”, “and”, “cat”]
输出:
[]

解题思路

采用与139题相同的思路,首先判断是否可分。若可分,采用回溯法找出所有答案。

代码

Python 3.6

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution:
def __init__(self):
self.res = []

def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:
max_len = 0
for word in wordDict:
if len(word) > max_len:
max_len = len(word)
dp = [0] * len(s)
for i in range(len(s)):
p = i
while p >= 0 and i - p <= max_len:
if (dp[p] and s[p + 1:i + 1] in wordDict) or (p == 0 and s[:i + 1] in wordDict):
dp[i] = 1
break
p -= 1
if dp[-1]:
self.find_all_res(s, wordDict, max_len, [])
return self.res

def find_all_res(self, s_cur, wordDict, max_len, cur_ls):
for i in range(1, max_len + 1):
if s_cur[:i] in wordDict:
if not s_cur[i:]:
self.res.append(" ".join(cur_ls + [s_cur[:i]]))
return
self.find_all_res(s_cur[i:], wordDict, max_len, cur_ls + [s_cur[:i]])