aboutsummaryrefslogtreecommitdiff
path: root/extra_char_string.c
blob: fbbde0e97f9a61a9ada2d345efea37f836e58d35 (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
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
// 2707. Extra Characters in a String
#include "leetcode.h"

/*
 * you are given a 0-indexed string 's' and a dictionary of words 'dictionary'.
 * you have to break 's' into one or more non-overlapping substrings that each
 * substring is present in 'dictionary'. there may be some extra characters in
 * 's' which are not present in any of the substrings. return the minimum number
 * of extra characters left over if you break up 's' optimally
 */

struct node {
  struct node *next[26];
  bool is_end;
};

void trie_init(struct node **head) {
  *head = (struct node *)calloc(1, sizeof(struct node));
}

void trie_insert(struct node *head, char *s) {
  while (*s) {
    char c = *s - 'a';
    if (!head->next[c])
      head->next[c] = (struct node *)calloc(1, sizeof(struct node));
    head = head->next[c];
    s++;
  }
  head->is_end = true;
}

int trie_search(struct node *head, char *s, int *len_out) {
  int cnt = 0, len = 0;
  while (*s) {
    char c = *s - 'a';
    if (!head->next[c])
      break;
    head = head->next[c];
    s++;
    len++;
    if (head->is_end) {
      len_out[cnt] = len;
      cnt++;
    }
  }
  return cnt;
}

void trie_free(struct node *head) {
  if (head) {
    for (int i = 0; i < 26; i++)
      trie_free(head->next[i]);
    free(head);
  }
}

int minExtra(int idx, char *s, struct node *trie, int *dp) {
  int lens[50], cnt = 0, min = INT_MAX, extra;
  if (!s[idx])
    return 0;
  if (dp[idx] != -1)
    return dp[idx];
  cnt = trie_search(trie, &s[idx], lens);
  for (int i = 0; i < cnt; i++) {
    extra = minExtra(idx + lens[i], s, trie, dp);
    min = fmin(min, extra);
  }
  extra = minExtra(idx + 1, s, trie, dp) + 1;
  min = fmin(min, extra);
  dp[idx] = min;
  return min;
}

int minExtraChar(char *s, char **dictionary, int dictionarySize) {
  struct node *trie = NULL;
  int min = 0, n = strlen(s), *dp = (int *)malloc(n * sizeof(int *));
  trie_init(&trie);
  for (int i = 0; i < n; i++)
    dp[i] = -1;
  for (int i = 0; i < dictionarySize; i++)
    trie_insert(trie, dictionary[i]);
  min = minExtra(0, s, trie, dp);
  trie_free(trie);
  free(dp);
  return min;
}

int main() {
  char *s1 = "leetscode", *d1[] = {"leet", "code", "leetcode"};
  char *s2 = "sayhelloworld", *d2[] = {"hello", "world"};
  printf("%d\n", minExtraChar(s1, (char **)d1, ARRAY_SIZE(d1))); // expect: 1
  printf("%d\n", minExtraChar(s2, (char **)d2, ARRAY_SIZE(d2))); // expect: 3
}