单词拆分 II
难度:
标签:
题目描述
Given a string s and a dictionary of strings wordDict, add spaces in s to construct a sentence where each word is a valid dictionary word. Return all such possible sentences in any order.
Note that the same word in the dictionary may be reused multiple times in the segmentation.
Example 1:
Input: s = "catsanddog", wordDict = ["cat","cats","and","sand","dog"] Output: ["cats and dog","cat sand dog"]
Example 2:
Input: s = "pineapplepenapple", wordDict = ["apple","pen","applepen","pine","pineapple"] Output: ["pine apple pen apple","pineapple pen apple","pine applepen apple"] Explanation: Note that you are allowed to reuse a dictionary word.
Example 3:
Input: s = "catsandog", wordDict = ["cats","dog","sand","and","cat"] Output: []
Constraints:
1 <= s.length <= 201 <= wordDict.length <= 10001 <= wordDict[i].length <= 10sandwordDict[i]consist of only lowercase English letters.- All the strings of
wordDictare unique. - Input is generated in a way that the length of the answer doesn't exceed 105.
代码结果
运行时间: 18 ms, 内存: 15.9 MB
/*
题目思路：
我们可以使用Java Stream和递归回溯来解决这个问题。首先使用动态规划来判断字符串s是否可以被分割成词典中的单词。然后通过递归和回溯的方法找到所有可能的分割方案。
*/
import java.util.*;
import java.util.stream.Collectors;
public class WordBreakIIStream {
public List<String> wordBreak(String s, List<String> wordDict) {
Set<String> wordSet = new HashSet<>(wordDict);
Map<Integer, List<String>> memo = new HashMap<>();
return dfs(s, 0, wordSet, memo);
}
private List<String> dfs(String s, int start, Set<String> wordSet, Map<Integer, List<String>> memo) {
if (memo.containsKey(start)) {
return memo.get(start);
}
List<String> res = new ArrayList<>();
if (start == s.length()) {
res.add("");
return res;
}
res = IntStream.range(start + 1, s.length() + 1)
.mapToObj(end -> s.substring(start, end))
.filter(wordSet::contains)
.flatMap(word -> dfs(s, end, wordSet, memo).stream().map(sub -> word + (sub.isEmpty() ? "" : " ") + sub))
.collect(Collectors.toList());
memo.put(start, res);
return res;
}
public static void main(String[] args) {
WordBreakIIStream solution = new WordBreakIIStream();
String s = "pineapplepenapple";
List<String> wordDict = Arrays.asList("apple", "pen", "applepen", "pine", "pineapple");
System.out.println(solution.wordBreak(s, wordDict));
}
}
解释
方法:
这个题解采用了回溯算法的思路。首先定义了一个回溯函数 back_track，它接受三个参数：当前待处理的字符串 s，当前已构建的句子 path，以及存储结果的列表 res。在回溯函数中，首先判断如果 s 为空，说明已经找到一个合法的句子，将 path 加入结果列表 res 中。然后遍历 s 的所有前缀，如果某个前缀出现在 wordDict 中，则继续递归调用回溯函数，处理剩余的字符串，并将当前前缀加入 path。最后在主函数中调用回溯函数，并返回结果列表 res。
时间复杂度:
O(2^n * nw)
空间复杂度:
O(2^n * n/w)
代码细节讲解
🦆
在回溯算法中，如何确保不会重复添加相同的句子到结果列表res中？
▷🦆
为什么选择使用回溯算法解决这个问题，而不是动态规划或其他算法？
▷🦆
在该算法中，如何处理wordDict中的单词重复使用的情况？
▷相关问题
单词拆分
给你一个字符串 s 和一个字符串列表 wordDict 作为字典。如果可以利用字典中出现的一个或多个单词拼接出 s 则返回 true。
注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。
示例 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
提示：
1 <= s.length <= 3001 <= wordDict.length <= 10001 <= wordDict[i].length <= 20s和wordDict[i]仅由小写英文字母组成wordDict中的所有字符串 互不相同
连接词
给你一个 不含重复 单词的字符串数组 words ，请你找出并返回 words 中的所有 连接词 。
连接词 定义为：一个完全由给定数组中的至少两个较短单词（不一定是不同的两个单词）组成的字符串。
示例 1：
输入：words = ["cat","cats","catsdogcats","dog","dogcatsdog","hippopotamuses","rat","ratcatdogcat"]
输出：["catsdogcats","dogcatsdog","ratcatdogcat"]
解释："catsdogcats" 由 "cats", "dog" 和 "cats" 组成;
"dogcatsdog" 由 "dog", "cats" 和 "dog" 组成;
"ratcatdogcat" 由 "rat", "cat", "dog" 和 "cat" 组成。
示例 2：
输入：words = ["cat","dog","catdog"] 输出：["catdog"]
提示：
1 <= words.length <= 1041 <= words[i].length <= 30words[i]仅由小写英文字母组成。words中的所有字符串都是 唯一 的。1 <= sum(words[i].length) <= 105