友情支持
如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜
|
|
有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。
公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。 |
140. 单词拆分 II
给定一个字符串 s 和一个字符串字典 wordDict，在字符串 s 中增加空格来构建一个句子，使得句子中所有的单词都在词典中。以任意顺序 返回所有这些可能的句子。
注意：词典中的同一个单词可能在分段中被重复使用多次。
示例 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"] 输出:[]
提示：
-
1 <= s.length <= 20 -
1 <= wordDict.length <= 1000 -
1 <= wordDict[i].length <= 10 -
s和wordDict[i]仅有小写英文字母组成 -
wordDict中所有字符串都 不同
思路分析
看到所有可能就知道是回溯。
-
一刷
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
29
30
31
32
33
34
35
/**
* @author D瓜哥 · https://www.diguage.com
* @since 2025-04-19 20:59:56
*/
public List<String> wordBreak(String s, List<String> wordDict) {
List<String> result = new ArrayList<>(s.length());
// 从 LinkedList 切换到 ArrayList，内存占用就大幅下降 43.77% → 91.82%
List<String> path = new ArrayList<>(s.length());
backtrack(s, wordDict, result, 0, path);
return result;
}
private void backtrack(String s, List<String> dict,
List<String> result, int index, List<String> path) {
if (s.length() < index) {
return;
}
if (index == s.length()) {
result.add(String.join(" ", path));
return;
}
for (String word : dict) {
int length = word.length();
if (s.length() < index + length) {
continue;
}
String substring = s.substring(index, index + length);
// 使用 word.equals(substring)，可以避免重复
if (word.equals(substring)) {
path.add(word);
backtrack(s, dict, result, index + length, path);
path.removeLast();
}
}
}