题目

给你两个 正整数 数组 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 的长度最大能达到 $5 \times 10^4$，如果使用暴力双重循环比对每一对 $(x, y)$，时间复杂度会达到 $O(N \times M) \approx 2.5 \times 10^9$，必然会超时（Time Limit Exceeded）。

但突破口在于提示中的 arr[i] <= 10^8。这意味着每个数字最多只有 8 位。基于这个特性，这道题有两种非常经典且高效的解题思路：

思路一：哈希表缓存前缀

既然数字最多只有 8 位，我们可以把 arr1 中所有数字的所有可能前缀全部拆解出来，存进一个哈希表（Hash Set）中。然后遍历 arr2，看 arr2 中数字的前缀是否存在于哈希表中。

具体步骤：

1. 构建前缀集合： 遍历 arr1，对于其中的每一个数字，不断地整除 10（x /= 10），并将得到的每一个结果（即前缀）存入哈希表。

2. 匹配最长前缀： 遍历 arr2，对于其中的每一个数字，同样不断地整除 10。

3. 查表： 每次除以 10 得到一个前缀时，去哈希表中查找。一旦在哈希表中找到了匹配项，说明这是当前数字与 arr1 共享的最长前缀（因为你是从完整的数字开始往下除，第一次碰到的公共前缀一定是最长的）。

4. 更新答案： 记录下匹配到的前缀的长度，并在所有匹配中取最大值。

复杂度分析：

• 时间复杂度： $O(N \cdot D + M \cdot D)$，其中 $N$ 和 $M$ 分别是数组长度，$D$ 是数字的最大位数（这里 $D \le 8$）。整体接近 $O(N + M)$，非常高效。

• 空间复杂度： $O(N \cdot D)$，用于存储 arr1 的所有前缀。

思路二：字典树 / 前缀树（Trie）

对于处理“前缀匹配”问题，字典树（Trie）是计算机科学中最正统的数据结构。我们可以把数字转换成字符串，把它们当作字符序列来构建树。

具体步骤：

1. 建树： 初始化一个空的字典树。将 arr1 中的所有数字转换成字符串，然后逐个字符（数字 0-9）插入到字典树中。树的每一条从根节点出发的路径都代表一个前缀。

2. 查询： 将 arr2 中的数字也转换成字符串。对于每一个字符串，从字典树的根节点开始往下走。

3. 匹配深度： 只要当前字符在树的当前层存在，就继续往下走，并记录走过的深度（即前缀长度）。如果在某一层字符不匹配了，说明当前数字的最长公共前缀就到此为止。

4. 更新答案： 记录所有字符串在树中能走到的最大深度。

复杂度分析：

• 时间复杂度： $O(N \cdot D + M \cdot D)$。虽然渐进复杂度与哈希表一样，但由于涉及到字符串转换和树节点遍历，常数级开销会略大于纯数字运算的哈希表。

• 空间复杂度： $O(N \cdot D \cdot 10)$（假设每个节点有 10 个子节点指向 0-9）。

具体代码

func longestCommonPrefix(arr1 []int, arr2 []int) int {

    hash := make(map[int]struct{})
    for _, num := range arr1 {
        for num != 0 {
            hash[num] = struct{}{}
            num /= 10
        }
    }

    ans := 0
    for _, num := range arr2 {
        for num != 0 {
            if _, exists := hash[num]; exists {
                ans = max(num, ans)
                break
            } else {
                num /= 10
            }
        }
    }

    result := 0
    for ans != 0 {
        ans /= 10
        result++
    }

    return result
}