目标
给你两个 正整数 数组 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 * 10^4
- 1 <= arr1[i], arr2[i] <= 10^8
思路
有两个数组 arr1 和 arr2，返回所有数对 (arr1[i], arr2[j]) 中最长公共前缀的长度。
将 arr1 中每个数字的前缀都计入哈希表，同时判断 arr2 中每个元素的的前缀是否在哈希表中，取前缀的最大长度即可。
或者可以将 arr1 的每个元素都加入 字典树，枚举 arr2 的每一个元素，计算其在字典树中公共前缀的最大长度。
代码
/**
* @date 2026-05-21 9:03
*/
public class LongestCommonPrefix3043 {
static class Trie {
public Trie[] children = new Trie[10];
public void insert(int num) {
String s = Integer.toString(num);
Trie cur = this;
for (int i = 0; i < s.length(); i++) {
int d = s.charAt(i) - '0';
if (cur.children[d] == null) {
cur.children[d] = new Trie();
}
cur = cur.children[d];
}
}
public int prefixLength(int num) {
String s = Integer.toString(num);
Trie cur = this;
int l = 0;
for (int i = 0; i < s.length(); i++) {
int d = s.charAt(i) - '0';
if (cur.children[d] == null) {
break;
}
cur = cur.children[d];
l++;
}
return l;
}
}
public int longestCommonPrefix(int[] arr1, int[] arr2) {
Trie root = new Trie();
for (int num : arr1) {
root.insert(num);
}
int res = 0;
for (int num : arr2) {
res = Math.max(res, root.prefixLength(num));
}
return res;
}
}
性能
