commit 570de43866205d3fc9a7f6a70c900642083b98f8
parent e0e5e33e5a335d61db2bf35c7d13bc60bd104fe7
Author: Jack Sangdahl <jack@pngu.org>
Date: Thu, 21 May 2026 08:16:55 +0300
3043. find the length of the longest common prefix
Diffstat:
2 files changed, 43 insertions(+), 130 deletions(-)
diff --git a/find_len_longest_prefix.c b/find_len_longest_prefix.c
@@ -11,107 +11,47 @@
* common prefix exists among them, return 0.
*/
-#define SUB_LEN ('9' + 1 - '0')
-
-struct trie_node {
- struct trie_node *next[SUB_LEN];
+struct map {
+ int id;
+ UT_hash_handle hh;
};
-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;
+int longestCommonPrefix(int *arr1, int arr1Size, int *arr2, int arr2Size) {
+ struct map *obj = NULL, *tmp, *iter;
+ int ans = 0, n;
+ for (int i = 0; i < arr1Size; i++)
+ for (int j = arr1[i]; j > 0; j /= 10) {
+ HASH_FIND_INT(obj, &j, tmp);
+ if (tmp)
+ continue;
+ tmp = (struct map *)malloc(sizeof(struct map));
+ *tmp = (struct map){j};
+ HASH_ADD_INT(obj, id, tmp);
}
- 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;
+ for (int i = 0; i < arr2Size; i++)
+ for (int j = arr2[i]; j > 0; j /= 10) {
+ HASH_FIND_INT(obj, &j, tmp);
+ if (!tmp)
+ continue;
+ n = floor(log10(j)) + 1;
+ ans = ans >= n ? ans : n;
+ ans = fmax(ans, n);
+ break;
+ }
+ HASH_ITER(hh, obj, iter, tmp) {
+ HASH_DEL(obj, iter);
+ free(iter);
}
- trie_free(pt);
- pt = NULL;
- return max_len;
+ return ans;
}
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
+ int r1 = longestCommonPrefix(a11, ARRAY_SIZE(a11), a21, ARRAY_SIZE(a21));
+ int r2 = longestCommonPrefix(a12, ARRAY_SIZE(a12), a22, ARRAY_SIZE(a22));
+ printf("%d\n", r1);
+ assert(r1 == 3);
+ printf("%d\n", r2);
+ assert(r2 == 0);
}
diff --git a/find_len_longest_prefix.py b/find_len_longest_prefix.py
@@ -1,5 +1,4 @@
# 3043. Find the Length of the Longest Common Prefix
-from bisect import bisect_left
"""
given two arrays with positive integers 'arr1' and 'arr2'. a prefix of a
@@ -12,41 +11,15 @@ common prefix exists among them, return 0.
"""
-class Solution(object):
- def longestCommonPrefix(self, arr1, arr2):
- """
- :type arr1: List[int]
- :type arr2: List[int]
- :rtype: int
- """
-
- def findCommonPrefixLength(x, y):
- common_prefix_length = 0
- min_length = min(len(x), len(y))
-
- for i in range(min_length):
- if x[i] == y[i]:
- common_prefix_length += 1
- else:
- break
-
- return common_prefix_length
-
- a = [str(x) for x in arr1]
- b = [str(x) for x in arr2]
-
- a.sort()
- b.sort()
-
- ans = 0
- n = len(a)
- for i in range(len(b)):
- idx = bisect_left(a, b[i])
- if idx < n:
- ans = max(ans, findCommonPrefixLength(a[idx], b[i]))
- if idx > 0:
- ans = max(ans, findCommonPrefixLength(a[idx - 1], b[i]))
- return ans
+class Solution:
+ def longestCommonPrefix(self, arr1: List[int], arr2: List[int]) -> int:
+ return max(
+ map(
+ len,
+ (f := lambda e: {str(v)[:i] for v in e for i in range(9)})(arr1)
+ & f(arr2),
+ )
+ )
if __name__ == "__main__":
