3043. Find the Length of the Longest Common Prefix
Description
You are 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. For example, 123
is a prefix of the integer 12345
, while 234
is not.
A common prefix of two integers a
and b
is an integer c
, such that c
is a prefix of both a
and b
. For example, 5655359
and 56554
have common prefixes 565
and 5655
while 1223
and 43456
do not have a common prefix.
You need to find the length of the longest common prefix between all pairs of integers (x, y)
such that x
belongs to arr1
and y
belongs to arr2
.
Return the length of the longest common prefix among all pairs. If no common prefix exists among them, return 0
.
Example 1:
Input: arr1 = [1,10,100], arr2 = [1000] Output: 3 Explanation: There are 3 pairs (arr1[i], arr2[j]): - The longest common prefix of (1, 1000) is 1. - The longest common prefix of (10, 1000) is 10. - The longest common prefix of (100, 1000) is 100. The longest common prefix is 100 with a length of 3.
Example 2:
Input: arr1 = [1,2,3], arr2 = [4,4,4] Output: 0 Explanation: There exists no common prefix for any pair (arr1[i], arr2[j]), hence we return 0. Note that common prefixes between elements of the same array do not count.
Constraints:
1 <= arr1.length, arr2.length <= 5 * 104
1 <= arr1[i], arr2[i] <= 108
Solutions
Solution 1: Hash Table
We can use a hash table to store all the prefixes of the numbers in arr1
. Then, we traverse all the numbers $x$ in arr2
. For each number $x$, we start from the highest bit and gradually decrease, checking whether it exists in the hash table. If it does, we have found a common prefix, and we can update the answer accordingly.
The time complexity is $O(m \times \log M + n \times \log N)$, and the space complexity is $O(m \times \log M)$. Here, $m$ and $n$ are the lengths of arr1
and arr2
respectively, and $M$ and $N$ are the maximum values in arr1
and arr2
respectively.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
|
1 2 3 4 5 |