题目链接 : https://leetcode-cn.com/problems/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. 单词拆分 | 题解链接
相关题型:139. 单词拆分
代码:
思路一:
class Solution:
def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:
import functools
if not wordDict:return []
wordDict = set(wordDict)
max_len = max(map(len, wordDict))
@functools.lru_cache(None)
def helper(s):
res = []
if not s:
res.append("")
return res
for i in range(len(s)):
if i < max_len and s[:i+1] in wordDict:
for t in helper(s[i+1:]):
if not t:
res.append(s[:i+1])
else:
res.append(s[:i+1] + " " + t)
return res
return helper(s)
java
class Solution {
public List<String> wordBreak(String s, List<String> wordDict) {
int max_len = 0;
for (String word : wordDict) max_len = Math.max(max_len, word.length());
return helper(s, max_len, wordDict, new HashMap<String, LinkedList<String>>());
}
private List<String> helper(String s, int max_len, List<String> wordDict, HashMap<String, LinkedList<String>> cache) {
if (cache.containsKey(s)) return cache.get(s);
LinkedList<String> res = new LinkedList<>();
if (s.length() == 0) {
res.add("");
return res;
}
for (int i = 0; i < s.length(); i++) {
if (i < max_len && wordDict.contains(s.substring(0, i + 1))) {
for (String tmp : helper(s.substring(i + 1), max_len, wordDict, cache))
res.add(s.substring(0, i + 1) + (tmp.isEmpty() ? "" : " ") + tmp);
}
}
cache.put(s, res);
return res;
}
}
