问题描述
给定一个字符串 s 和字符串数组 wordDict，要求将字符串 s 切割成单词组成的句子，其中每个单词都来自 wordDict 中的字符串，wordDict 中的字符串可以重复使用。返回所有满足要求的句子列表。题目链接：**点我**
样例输入输出
输入：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”]
问题解法
解法一：单纯回溯（超时）
最直观简单的做法就是使用回溯算法，没有使用记忆化搜索进行剪枝，这也算是暴力的一种做法吧。代码如下
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
36
37
38
39
| class Solution
{
public List<String> wordBreak(String s, List<String> wordDict)
{
List<String> result = new ArrayList<>();
wordBreak(s, 0, wordDict, new ArrayList<>(), result);
return result;
}
private void wordBreak(String str, int startIndex, List<String> wordDict, List<String> current, List<String> result)
{
if (startIndex == str.length())
{
result.add(convert(current));
return;
}
for (String word : wordDict)
{
if (str.startsWith(word, startIndex))
{
current.add(word);
wordBreak(str, startIndex + word.length(), wordDict, current, result);
current.remove(current.size() - 1);
}
}
}
private String convert(List<String> strList)
{
StringBuilder sb = new StringBuilder();
for (String str : strList)
{
sb.append(str).append(" ");
}
return sb.toString().trim();
}
}
|
解法二：回溯+记忆化搜索剪枝
单纯使用回溯算法暴力搜索超时了，所以加上记忆化搜索，对不满足要求的重复搜索的过程进行剪枝处理，减少时间损耗。代码如下
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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
| class Solution
{
public List<String> wordBreak(String s, List<String> wordDict)
{
List<String> result = new ArrayList<>();
int[] flags = new int[s.length() + 1];
wordBreak(s, 0, wordDict, flags, new ArrayList<>(), result);
return result;
}
private boolean wordBreak(String str, int startIndex, List<String> wordDict, int[] flags, List<String> current, List<String> result)
{
if (flags[startIndex] == -1)
{
return false;
}
if (startIndex == str.length())
{
result.add(convert(current));
return true;
}
boolean isFind = false;
for (String word : wordDict)
{
if (str.startsWith(word, startIndex))
{
current.add(word);
if (wordBreak(str, startIndex + word.length(), wordDict, flags, current, result))
{
isFind = true;
}
if (!isFind)
{
flags[startIndex] = -1;
}
current.remove(current.size() - 1);
}
}
return isFind;
}
private String convert(List<String> strList)
{
StringBuilder sb = new StringBuilder();
for (String str : strList)
{
sb.append(str).append(" ");
}
return sb.toString().trim();
}
}
|