aboutsummaryrefslogtreecommitdiff
path: root/longest_string_chain.c
blob: 3053fc60370dce55439e5a07f6af24616ebbc0cb (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
// 1048. Longest String Chain
#include <math.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

/*
 * you are given an array of 'words' where each word consists of lowercase
 * english letters. 'word[a]' is a predecessor of 'word[b]' if and only if we
 * can insert exactly one letter anywhere in 'word[a]' without changing the
 * order of the other characters to make it equal to 'word[b]'. return the
 * length of the longest possible word chain with words chosen from the given
 * list of words.
 */

int cmp(const void *a, const void *b) {
  char *s1 = *(char **)a;
  char *s2 = *(char **)b;
  return strlen(s1) - strlen(s2);
}

bool strcmp_ex(char *s1, char *s2) {
  int len1 = strlen(s1), len2 = strlen(s2);
  int idx1 = 0, idx2 = 0;
  while (idx1 < len1 && idx2 < len2) {
    if (s1[idx1] == s2[idx2]) {
      idx1++;
      idx2++;
    } else {
      idx2++;
    }
  }
  if (idx1 != len1)
    return false;
  else
    return true;
}

// int longestStrChain(char **words, int words_size) {
int longestStrChain(int c, char words[][c], int words_size) {
  qsort(words, words_size, sizeof(char *), cmp);
  int *dp = malloc(words_size * sizeof(int));
  int i, j, m, n, lsc = 1;
  dp[0] = 1;
  for (i = 1; i < words_size; i++) {
    if (strlen(words[i]) == 1)
      dp[i] = 1;
    else
      break;
  }
  for (j = i; j < words_size; j++) {
    dp[j] = 1;
    for (m = j - 1; m >= 0; m--) {
      if (strlen(words[m]) == strlen(words[j]))
        continue;
      if (strlen(words[m]) < strlen(words[j]) - 1)
        break;
      if (strcmp_ex(words[m], words[j]))
        dp[j] = fmax(dp[m] + 1, dp[j]);
    }
    lsc = fmax(lsc, dp[j]);
  }
  free(dp);
  return lsc;
}

int main() {
  char w1[][4] = {"a", "b", "ba", "bca", "bda", "bdca"};
  char w2[][6] = {"xbc", "pcxbcf", "xb", "cxbc", "pcxbc"};
  char w3[][5] = {"abcd", "dbqca"};
  printf("%d\n", longestStrChain(4, w1, 6)); // expect: 4
  printf("%d\n", longestStrChain(6, w2, 6)); // expect: 4
  printf("%d\n", longestStrChain(5, w3, 6)); // expect: 4
}