给出一个字符串 s 和一个词表 wordDict，按照词表对字符串进行切分，排除干扰元素，返回一个子串数组，要求切割后的子串尽可能地覆盖原字符串。
示例 1：
输入:
s = “hecatsanddogllo”
wordDict = [“cat”, “cats”, “and”, “sand”, “dog”]
输出:
[“cats and dog”]
[“cat sand dog”]
任意一个都可。
示例 2：
输入:
s = “hcatsandog”
wordDict = [“cats”, “sandog”]
输出:
[ “sandog”]
示例 3：
输入:
s = “catsandog”, wordDict = [“cats”, “dog”, “sand”, “and”, “cat”]
输出:
[“cats”, “and”]
[“cats”, “dog”]
[“cat”, “sand”]
任意一个都可。
1
2
3
public List wordBreak(String s, Set 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
36
37
38
39
40
41
42
43
44
45
46
47
48
/**
- dp[i]：表示s中前i个字符最大可以切割的子字符串数组的长度和
- result[i]存储的 List为： s中前i个字符最大可以切割的子字符串数组
- 举个例子：s = “catsandog”, wordDict = [“cats”, “dog”, “sand”, “and”, “cat”]
- 因为 ca 没有出现在 wordDict 中，因此 对于s中的前 0/1/2 个字符来说，
- dp[0]==dp[1]==dp[2]==0 result[0]==result[1]==result[2]==new ArrayList<>()
- 当i为3时，cat符合条件，因此 dp[3] = 3 result[3] = [“cat”]
- 当i为4时，cats符合条件，因此 dp[4] = 4 result[4] = [“cats”]
- 当i为5时，以s中第5个字符’a’为结尾的子字符串没有存在词表里，因此 dp[5] = dp[4] result[5] = result[4] = [“cats”]
- 同理 dp[6] = dp[5] result[6] = result[5] = [“cats”]
- 当i为7时，s 中 第 4个字符到第7个字符 组成的 子字符串 sand 存在于 词典里，
- 因此 dp[7] = Math.max(dp[6], dp[4-1] + 7 - 4 + 1) 而 result[7] 也会根据dp[7]的选择，
- 如果 dp[7] == dp[6] 那么 result[7] = result[6] = [“cats”]
- 否则的话，result[7] = result[4-1] + s中第4个字符到第7个字符组成的子字符串 = [“cat”, “sand”]
- 后面的依次类推，最后返回 result[i] 中最后一个 List 即为所求。
*/
public static List wordBreak(String s, Set wordDict) {
int length = s.length();
int dp = new int[length + 1];
List result = new ArrayList[length + 1];
result[0] = new ArrayList<>();
dp[0] = 0;
for (int right = 1; right <= length; ++right) {
int index = -1;
int maxLen = 0;
for (int left = 1; left <= right; ++left) {
if (wordDict.contains(s.substring(left - 1, right))) {
int currentLen = right - left + 1 + dp[left - 1];
if (maxLen < currentLen) {
maxLen = currentLen;
index = left;
}
}
}
List currentList;
if (index == -1 || maxLen < dp[right - 1]) {
dp[right] = dp[right - 1];
currentList = new ArrayList<>(result[right - 1]);
} else {
dp[right] = maxLen;
currentList = new ArrayList<>(result[index - 1]);
currentList.add(s.substring(index - 1, right));
}
result[right] = currentList;
}
return result[length];
}