LeetCode 题解工作台
最长公共前缀的长度
给你两个 正整数 数组 arr1 和 arr2 。 正整数的 前缀 是其 最左边 的一位或多位数字组成的整数。例如， 123 是整数 12345 的前缀，而 234 不是 。 设若整数 c 是整数 a 和 b 的 公共前缀 ，那么 c 需要同时是 a 和 b 的前缀。例如， 5655359 和 56…
4
题型
6
代码语言
3
相关题
当前训练重点
中等 · 数组·哈希·扫描
答案摘要
我们可以使用哈希表来存储 `arr1` 中的所有数字的前缀，然后遍历 `arr2` 中的所有数字 ，对于每个数字 ，我们从最高位开始逐渐减小，判断是否存在于哈希表中，如果存在，那么我们就找到了一个公共前缀，此时更新答案即可。 时间复杂度 $O(m \times \log M + n \times \log N)$，空间复杂度 $O(m \times \log M)$。其中 和 分别是 `arr…
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·哈希·扫描 题型思路
题目描述
给你两个 正整数 数组 arr1 和 arr2 。
正整数的 前缀 是其 最左边 的一位或多位数字组成的整数。例如，123 是整数 12345 的前缀，而 234 不是 。
设若整数 c 是整数 a 和 b 的 公共前缀 ，那么 c 需要同时是 a 和 b 的前缀。例如，5655359 和 56554 有公共前缀 565 和 5655，而 1223 和 43456 没有 公共前缀。
你需要找出属于 arr1 的整数 x 和属于 arr2 的整数 y 组成的所有数对 (x, y) 之中最长的公共前缀的长度。
返回所有数对之中最长公共前缀的长度。如果它们之间不存在公共前缀，则返回 0 。
示例 1：
输入：arr1 = [1,10,100], arr2 = [1000] 输出：3 解释：存在 3 个数对 (arr1[i], arr2[j]) ： - (1, 1000) 的最长公共前缀是 1 。 - (10, 1000) 的最长公共前缀是 10 。 - (100, 1000) 的最长公共前缀是 100 。 最长的公共前缀是 100 ，长度为 3 。
示例 2：
输入：arr1 = [1,2,3], arr2 = [4,4,4] 输出：0 解释：任何数对 (arr1[i], arr2[j]) 之中都不存在公共前缀，因此返回 0 。 请注意，同一个数组内元素之间的公共前缀不在考虑范围内。
提示：
1 <= arr1.length, arr2.length <= 5 * 1041 <= arr1[i], arr2[i] <= 108
解题思路
方法一：哈希表
我们可以使用哈希表来存储 arr1 中的所有数字的前缀，然后遍历 arr2 中的所有数字 ，对于每个数字 ，我们从最高位开始逐渐减小，判断是否存在于哈希表中，如果存在，那么我们就找到了一个公共前缀，此时更新答案即可。
时间复杂度 ，空间复杂度 。其中 和 分别是 arr1 和 arr2 的长度，而 和 分别是 arr1 和 arr2 中的最大值。
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
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(m * d + n * d) where m and n are array sizes and d is the maximum digit length, effectively O(m + n) due to constant prefix generation. Space complexity is O(m * d) for storing all arr1 prefixes in the HashSet. |
| 空间 | O(m \cdot d) = O(m) |
面试官常问的追问
外企场景- question_mark
Ask candidates about generating prefixes efficiently without pairwise comparison.
- question_mark
Probe knowledge of HashSet lookup and why it reduces complexity.
- question_mark
Check understanding of integer prefix handling and array scanning trade-offs.
常见陷阱
外企场景- error
Failing to stop prefix comparison at the first mismatch leading to wrong lengths.
- error
Using nested loops for all pairs instead of HashSet, causing TLE on large arrays.
- error
Ignoring single-digit or full-length prefixes, missing edge cases.
进阶变体
外企场景- arrow_right_alt
Find the longest common prefix among multiple arrays instead of two.
- arrow_right_alt
Return the actual longest common prefix value rather than just the length.
- arrow_right_alt
Apply the prefix check to strings instead of integers, maintaining the hash lookup pattern.