aboutsummaryrefslogtreecommitdiff
path: root/word_break2.c
blob: 41dcfd8f5af547998d7e0e9f726d3e8d8158bfe5 (plain)
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");
}