diff options
-rw-r--r-- | find_len_longest_prefix.c | 96 |
1 files changed, 90 insertions, 6 deletions
diff --git a/find_len_longest_prefix.c b/find_len_longest_prefix.c index 2d8bb36..fa2c764 100644 --- a/find_len_longest_prefix.c +++ b/find_len_longest_prefix.c @@ -11,17 +11,101 @@ * common prefix exists among them, return 0. */ -struct node { - char val; - int height; - struct node *children[10]; +#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 node *root; + struct trie_node *ptn; }; -int longestCommonPrefix(int *arr1, int arr1_size, int *arr2, int arr2_size) {} +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}; |