Welcome to Subscribe On Youtube
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 a common prefix 565 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.
-
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; } } -
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; } }; -
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 -
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 } -
function longestCommonPrefix(arr1: number[], arr2: number[]): number { const s: Set<number> = new Set<number>(); for (let x of arr1) { for (; x; x = (x / 10) | 0) { s.add(x % 10); } } let ans: number = 0; for (let x of arr2) { for (; x; x = (x / 10) | 0) { if (s.has(x % 10)) { ans = Math.max(ans, Math.floor(Math.log10(x)) + 1); } } } return ans; } -
/** * @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; };