aboutsummaryrefslogtreecommitdiff
path: root/find_len_longest_prefix.c
blob: fa2c764a1966247b50aff1e216abd1a1c5b44802 (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
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
// 3043. Find the Length of the Longest Common Prefix
#include "leetcode.h"

/*
 * given two arrays with positive integers 'arr1' and 'arr2'. a prefix of a
 * positive integer is an integer formed by one or more of its digits, starting
 * from its leftmost digit. a common prefix of two integers 'a' and 'b' is an
 * integer 'c' such that is a prefix of both a and b. for example 6555359 and
 * 56554 have a common prefix 565 while q223 and 43456 do not have a common
 * prefix. return the length of the longest common prefix among all pairs. if no
 * common prefix exists among them, return 0.
 */

#define SUB_LEN ('9' + 1 - '0')

struct trie_node {
  struct trie_node *next[SUB_LEN];
};

struct trie_node *trie_node_init(void) {
  return (struct trie_node *)calloc(1, sizeof(struct trie_node));
}

void trie_node_free(struct trie_node *const pt) {
  assert(pt);
  for (int i = 0; i < SUB_LEN; i++)
    if (pt->next[i]) {
      trie_node_free(pt->next[i]);
      pt->next[i] = NULL;
    }
  free(pt);
}

struct trie {
  struct trie_node *ptn;
};

struct trie *trie_init(void) {
  struct trie *pt = (struct trie *)malloc(sizeof(struct trie));
  if (!pt)
    return NULL;
  pt->ptn = trie_node_init();
  if (pt->ptn) {
    free(pt);
    pt = NULL;
  }
  return pt;
}

void trie_free(struct trie *pt) {
  trie_node_free(pt->ptn);
  pt->ptn = NULL;
  free(pt);
}

void trie_insert(struct trie *const pt, const int8_t *const digit,
                 const int digit_size) {
  struct trie_node *ptn1 = pt->ptn;
  for (int i = 0; i < digit_size; i++) {
    assert(digit[i] >= 0 && digit[i] <= 9);
    if (!ptn1->next[digit[i]])
      ptn1->next[digit[i]] = trie_node_init();
    ptn1 = ptn1->next[digit[i]];
  }
}

int trie_lcp(struct trie *const pt, const int8_t *const digit,
             const int digit_size) {
  const struct trie_node *ptn1 = pt->ptn;
  for (int i = 0; i < digit_size; i++) {
    assert(digit[i] >= 0 && digit[i] <= 9);
    if (!ptn1->next[digit[i]])
      return i;
    ptn1 = ptn1->next[digit[i]];
  }
  return digit_size;
}

static int num_to_dig(const int num, int8_t *const digit_buf,
                      const int digit_buf_size) {
  int digit_size = 0;
  for (int i = 0; i; i /= 10) {
    digit_size++;
    assert(digit_buf_size - digit_size >= 0);
    digit_buf[digit_buf_size - digit_size] = i % 10;
  }
  return digit_size;
}

int longestCommonPrefix(int *arr1, int arr1_size, int *arr2, int arr2_size) {
  int8_t digit_buf[10];
  int digit_size;
  struct trie *pt = trie_init();
  for (int i = 0; i < arr1_size; i++) {
    digit_size = num_to_dig(arr1[i], digit_buf, 10);
    trie_insert(pt, digit_buf + 10 - digit_size, digit_size);
  }
  int max_len = 0;
  for (int i = 0; i < arr2_size; i++) {
    digit_size = num_to_dig(arr2[i], digit_buf, 10);
    const int curr_size = trie_lcp(pt, digit_buf + 10 - digit_size, digit_size);
    if (curr_size > max_len)
      max_len = curr_size;
  }
  trie_free(pt);
  pt = NULL;
  return max_len;
}

int main() {
  int a11[] = {1, 10, 100}, a21[] = {1000};
  int a12[] = {1, 2, 3}, a22[] = {4, 4, 4};
  printf("%d\n", longestCommonPrefix(a11, ARRAY_SIZE(a11), a21,
                                     ARRAY_SIZE(a21))); // expect: 3
  printf("%d\n", longestCommonPrefix(a12, ARRAY_SIZE(a12), a22,
                                     ARRAY_SIZE(a22))); // expect: 3
}