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 * 1041 <= 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.
Python3
class Solution:
def longestCommonPrefix(self, arr1: List[int], arr2: List[int]) -> int:
s = set()
for x in arr1:
while x:
s.add(x)
x //= 10
ans = 0
for x in arr2:
while x:
if x in s:
ans = max(ans, len(str(x)))
break
x //= 10
return ans
Java
class Solution {
public int longestCommonPrefix(int[] arr1, int[] arr2) {
Set<Integer> s = new HashSet<>();
for (int x : arr1) {
for (; x > 0; x /= 10) {
s.add(x);
}
}
int ans = 0;
for (int x : arr2) {
for (; x > 0; x /= 10) {
if (s.contains(x)) {
ans = Math.max(ans, String.valueOf(x).length());
break;
}
}
}
return ans;
}
}
C++
class Solution {
public:
int longestCommonPrefix(vector<int>& arr1, vector<int>& arr2) {
unordered_set<int> s;
for (int x : arr1) {
for (; x; x /= 10) {
s.insert(x);
}
}
int ans = 0;
for (int x : arr2) {
for (; x; x /= 10) {
if (s.count(x)) {
ans = max(ans, (int) log10(x) + 1);
break;
}
}
}
return ans;
}
};
Go
func longestCommonPrefix(arr1 []int, arr2 []int) (ans int) {
s := map[int]bool{}
for _, x := range arr1 {
for ; x > 0; x /= 10 {
s[x] = true
}
}
for _, x := range arr2 {
for ; x > 0; x /= 10 {
if s[x] {
ans = max(ans, int(math.Log10(float64(x)))+1)
break
}
}
}
return
}
TypeScript
function longestCommonPrefix(arr1: number[], arr2: number[]): number {
const s: Set<number> = new Set<number>();
for (let x of arr1) {
for (; x; x = Math.floor(x / 10)) {
s.add(x);
}
}
let ans: number = 0;
for (let x of arr2) {
for (; x; x = Math.floor(x / 10)) {
if (s.has(x)) {
ans = Math.max(ans, Math.floor(Math.log10(x)) + 1);
}
}
}
return ans;
}
JavaScript
/**
* @param {number[]} arr1
* @param {number[]} arr2
* @return {number}
*/
var longestCommonPrefix = function (arr1, arr2) {
const s = new Set();
for (let x of arr1) {
for (; x; x = Math.floor(x / 10)) {
s.add(x);
}
}
let ans = 0;
for (let x of arr2) {
for (; x; x = Math.floor(x / 10)) {
if (s.has(x)) {
ans = Math.max(ans, Math.floor(Math.log10(x)) + 1);
}
}
}
return ans;
};