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
}
|