0140. 单词拆分 II【困难】
1. 📝 题目描述
给定一个字符串 s 和一个字符串字典 wordDict,在字符串 s 中增加空格来构建一个句子,使得句子中所有的单词都在词典中。以任意顺序返回所有这些可能的句子。
注意:词典中的同一个单词可能在分段中被重复使用多次。
示例 1:
txt
输入:s = "catsanddog", wordDict = ["cat","cats","and","sand","dog"]
输出:["cats and dog","cat sand dog"]1
2
2
示例 2:
txt
输入:s = "pineapplepenapple", wordDict = ["apple","pen","applepen","pine","pineapple"]
输出:["pine apple pen apple","pineapple pen apple","pine applepen apple"]1
2
2
解释: 注意你可以重复使用字典中的单词。
示例 3:
txt
输入:s = "catsandog", wordDict = ["cats","dog","sand","and","cat"]
输出:[]1
2
2
提示:
1 <= s.length <= 201 <= wordDict.length <= 10001 <= wordDict[i].length <= 10s和wordDict[i]仅有小写英文字母组成wordDict中所有字符串都不同
2. 🎯 s.1 - DP 预处理 + DFS 回溯
c
/**
* Note: The returned array must be malloced, assume caller calls free().
*/
char** result;
int resultSize;
bool dp[21];
int pathStart[21], pathEnd[21]; // 记录路径中每个词的起止位置
int pathSize;
int N;
bool hasWord(const char* s, int start, int end, char** wordDict, int dictSize) {
int len = end - start;
for (int i = 0; i < dictSize; i++) {
if ((int)strlen(wordDict[i]) == len && strncmp(s + start, wordDict[i], len) == 0)
return true;
}
return false;
}
void dfs(const char* s, int start, char** wordDict, int dictSize) {
if (start == N) {
// 拼接路径中的每个词,词间加空格
char* sentence = (char*)malloc(50 * sizeof(char));
int pos = 0;
for (int i = 0; i < pathSize; i++) {
if (i > 0) sentence[pos++] = ' ';
int len = pathEnd[i] - pathStart[i];
memcpy(sentence + pos, s + pathStart[i], len);
pos += len;
}
sentence[pos] = '\0';
result[resultSize++] = sentence;
return;
}
for (int end = start + 1; end <= N; end++) {
// 剪枝:只走 dp[end] 可达的分支
if (dp[end] && hasWord(s, start, end, wordDict, dictSize)) {
pathStart[pathSize] = start;
pathEnd[pathSize] = end;
pathSize++;
dfs(s, end, wordDict, dictSize);
pathSize--;
}
}
}
char** wordBreak(char* s, char** wordDict, int wordDictSize, int* returnSize) {
N = strlen(s);
memset(dp, 0, sizeof(dp));
dp[0] = true;
for (int i = 1; i <= N; i++) {
for (int j = 0; j < i; j++) {
if (dp[j] && hasWord(s, j, i, wordDict, wordDictSize)) {
dp[i] = true;
break;
}
}
}
result = (char**)malloc(10000 * sizeof(char*));
resultSize = 0;
pathSize = 0;
dfs(s, 0, wordDict, wordDictSize);
*returnSize = resultSize;
return result;
}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
58
59
60
61
62
63
64
65
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
58
59
60
61
62
63
64
65
js
/**
* @param {string} s
* @param {string[]} wordDict
* @return {string[]}
*/
var wordBreak = function (s, wordDict) {
const n = s.length
const wordSet = new Set(wordDict)
// dp[i] = true 表示 s[0..i-1] 可被字典中的单词拆分
const dp = new Array(n + 1).fill(false)
dp[0] = true
for (let i = 1; i <= n; i++) {
for (let j = 0; j < i; j++) {
if (dp[j] && wordSet.has(s.slice(j, i))) {
dp[i] = true
break
}
}
}
const res = []
const path = []
const dfs = (start) => {
if (start === n) {
res.push(path.join(' '))
return
}
for (let end = start + 1; end <= n; end++) {
// 剪枝:只走 dp[end] 可达的分支
if (dp[end] && wordSet.has(s.slice(start, end))) {
path.push(s.slice(start, end))
dfs(end)
path.pop()
}
}
}
dfs(0)
return res
}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
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
py
class Solution:
def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:
n = len(s)
word_set = set(wordDict)
# dp[i] = True 表示 s[0..i-1] 可被字典中的单词拆分
dp = [False] * (n + 1)
dp[0] = True
for i in range(1, n + 1):
for j in range(i):
if dp[j] and s[j:i] in word_set:
dp[i] = True
break
res: List[str] = []
path: List[str] = []
def dfs(start: int) -> None:
if start == n:
res.append(' '.join(path))
return
for end in range(start + 1, n + 1):
# 剪枝:只走 dp[end] 可达的分支
if dp[end] and s[start:end] in word_set:
path.append(s[start:end])
dfs(end)
path.pop()
dfs(0)
return res1
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
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
- 时间复杂度:
,DP 预处理 ,DFS 只遍历可达位置,额外开销正比于输出总长度 - 空间复杂度:
,DP 数组和递归栈深度均为 (不计输出)
算法思路:
- DP 预处理:
dp[i]表示s[0..i-1]能否被字典中的单词拆分, - DFS 回溯
- 从位置 0 出发开始扫描,扫到结尾时记录结果
- 枚举每个合法结尾
end且s[start..end-1]在字典中时才递归 - 合法结尾
end是指dp[end] == true的位置(借助 DP 结果剪掉所有无法到达终点的死路)
- 到达末尾时将路径中的单词拼接成句子加入结果集
2.1. DP 状态转移方程
| 符号 | 含义 |
|---|---|
| 前缀 | |
| 逻辑或(OR),遍历所有满足 | |
| 前缀 | |
| 逻辑与(AND) | |
| 字符串 | |
| 该子串是否存在于给定的词典中 |