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
|
// 140. Word Break II
#include "leetcode.h"
/*
* 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 mutliple times in the segmentation.
*/
void dfs(char *s, char **dict, int dict_size, char **res, int *return_size,
int *idx, int map_size, int len) {
if (*s == '\0') {
res[*return_size] = (char *)malloc(len * sizeof(char));
char *head = res[*return_size];
for (int i = 0; i < map_size; ++i) {
int n = strlen(dict[idx[i]]);
strcpy(head, dict[idx[i]]);
head[n] = ' ';
head += len++;
}
res[*return_size][len - 1] = '\0';
++(*return_size);
return;
}
for (int i = 0; i < dict_size; ++i) {
int n = strlen(dict[i]);
if (!strncmp(s, dict[i], n)) {
idx[map_size] = i;
dfs(s + n, dict, dict_size, res, return_size, idx, map_size + 1,
len + n + 1);
}
}
}
char **wordBreak(char *s, char **wordDict, int wordDictSize, int *returnSize) {
char **ans = (char **)malloc(500 * sizeof(char *));
int *idx = (int *)malloc(500 * sizeof(int));
*returnSize = 0;
dfs(s, wordDict, wordDictSize, ans, returnSize, idx, 0, 0);
free(idx);
return ans;
}
int main() {
char *s1 = "catsanddog", *s2 = "pineapplepenapple", *s3 = "catsandog";
char *wd1[] = {"cat", "cats", "and", "sand", "dog"},
*wd2[] = {"apple", "pen", "applepen", "pine", "pineapple"},
*wd3[] = {"cats", "dog", "sand", "and", "cat"};
int rs1, rs2, rs3;
char **wb1 = wordBreak(s1, (char **)wd1, ARRAY_SIZE(wd1), &rs1);
char **wb2 = wordBreak(s2, (char **)wd2, ARRAY_SIZE(wd2), &rs2);
char **wb3 = wordBreak(s3, (char **)wd3, ARRAY_SIZE(wd3), &rs3);
for (int i = 0; i < rs1; i++)
printf("%s ", wb1[i]); // expect: "cats and dog","cat sand dog"
printf("\n");
for (int i = 0; i < rs2; i++)
printf("%s ", wb2[i]); // "pine apple pen apple","pineapple pen apple","pine
// applepen apple"
printf("\n");
for (int i = 0; i < rs3; i++)
printf("%s ", wb3[i]); // expect: null
printf("\n");
}
|