aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--find_len_longest_prefix.c96
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};