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
66
67
68
|
// 139. Word Break
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
/*
* given a string 's' and a dictionary of strings 'word_dict', return 'true' if
* 's' can be segmented into a space-separated sequence of one or more
* dictionary words. note that the same word in the dictionary may be reused
* multiple times in the segmentation.
*/
bool process(char *s, char **word_dict, int word_dict_size, int *word_dict_len,
int len) {
bool res = false;
if (!len)
return true;
for (int i = 0; i < word_dict_size; i++)
if (!strncmp(s, word_dict[i], word_dict_len[i]))
if (process(&s[word_dict_len[i]], word_dict, word_dict_size,
word_dict_len, len - word_dict_len[i])) {
res = true;
break;
}
return res;
}
static int string_compare(const void *p1, const void *p2) {
return strlen(*(char **)p1) - strlen(*(char **)p2);
}
bool wordBreak(char *s, char **word_dict, int word_dict_size) {
int i, j, n = strlen(s);
bool *flag = (bool *)calloc(n + 1, sizeof(bool));
qsort(word_dict, word_dict_size, sizeof(char *), string_compare);
int *word_dict_len = (int *)malloc(word_dict_size * sizeof(int));
for (i = 0; i < word_dict_size; i++)
word_dict_len[i] = strlen(word_dict[i]);
int size, begin;
flag[0] = true;
for (i = 1; i <= n; i++) {
for (j = 0; j < word_dict_size; j++) {
if (word_dict_len[j] > i)
break;
else {
begin = i - word_dict_len[j];
if (!strncmp(word_dict[j], &s[begin], word_dict_len[j]))
if (flag[begin]) {
flag[i] = true;
break;
}
}
}
}
bool ans = flag[n];
free(flag), free(word_dict_len);
return ans;
}
int main() {
char s1[] = {"leetcode"}, s2[] = {"applepenapple"}, s3[] = {"catsanddog"};
char wd1[2][4] = {{"leet"}, {"code"}}, wd2[2][5] = {{"apple"}, {"pen"}},
wd3[5][4] = {{"cats"}, {"dog"}, {"sand"}, {"and"}, {"cat"}};
printf("%d\n", wordBreak(s1, wd1, 2)); // expect: 1
printf("%d\n", wordBreak(s2, wd2, 2)); // expect: 1
printf("%d\n", wordBreak(s3, wd3, 5)); // expect: 0
}
|