Medium

题目描述

给你两个由正整数组成的数组 arr1 和 arr2。

正整数的前缀是由它的一个或多个数字组成的整数，从最左边的数字开始。例如，123 是整数 12345 的前缀，而 234 不是。

两个整数 a 和 b 的公共前缀是一个整数 c，使得 c 是 a 和 b 的前缀。例如，5655359 和 56554 有公共前缀 565 和 5655，而 1223 和 43456 没有公共前缀。

你需要找到所有 arr1[i] 和 arr2[j] 配对中最长公共前缀的长度。

如果它们之间不存在公共前缀，返回 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

解题思路

这道题有两种主要解法：

方法一：哈希表（推荐）

核心思想是将一个数组的所有可能前缀存储在哈希表中，然后遍历另一个数组的前缀进行匹配。

  1. 将 arr1 中每个数的所有前缀存入哈希表
  2. 遍历 arr2 中每个数的所有前缀，检查是否在哈希表中存在
  3. 记录找到的最长公共前缀长度

时间复杂度：O(n × log(max_val))，其中 n 是数组长度，log(max_val) 是数字的位数。

方法二：字典树（Trie）

可以构建字典树来存储前缀，但对于这道题，哈希表方法更简洁高效。

具体实现中，我们通过不断除以10来获取一个数的所有前缀，例如对于123，依次得到1、12、123。注意要从最长的前缀开始检查，这样能更早找到最长匹配。

代码实现

class Solution {
public:
    int longestCommonPrefix(vector<int>& arr1, vector<int>& arr2) {
        unordered_set<int> prefixSet;
        
        // 将arr1中所有数的所有前缀存入哈希表
        for (int num : arr1) {
            while (num > 0) {
                prefixSet.insert(num);
                num /= 10;
            }
        }
        
        int maxLen = 0;
        
        // 检查arr2中每个数的前缀
        for (int num : arr2) {
            while (num > 0) {
                if (prefixSet.count(num)) {
                    maxLen = max(maxLen, (int)to_string(num).length());
                    break; // 找到匹配后跳出，因为当前num是最长的可能前缀
                }
                num /= 10;
            }
        }
        
        return maxLen;
    }
};

class Solution:
    def longestCommonPrefix(self, arr1: List[int], arr2: List[int]) -> int:
        prefix_set = set()
        
        # 将arr1中所有数的所有前缀存入集合
        for num in arr1:
            while num > 0:
                prefix_set.add(num)
                num //= 10
        
        max_len = 0
        
        # 检查arr2中每个数的前缀
        for num in arr2:
            while num > 0:
                if num in prefix_set:
                    max_len = max(max_len, len(str(num)))
                    break  # 找到匹配后跳出，因为当前num是最长的可能前缀
                num //= 10
        
        return max_len

public class Solution {
    public int LongestCommonPrefix(int[] arr1, int[] arr2) {
        HashSet<int> prefixSet = new HashSet<int>();
        
        // 将arr1中所有数的所有前缀存入哈希表
        foreach (int num in arr1) {
            int temp = num;
            while (temp > 0) {
                prefixSet.Add(temp);
                temp /= 10;
            }
        }
        
        int maxLen = 0;
        
        // 检查arr2中每个数的前缀
        foreach (int num in arr2) {
            int temp = num;
            while (temp > 0) {
                if (prefixSet.Contains(temp)) {
                    maxLen = Math.Max(maxLen, temp.ToString().Length);
                    break; // 找到匹配后跳出，因为当前temp是最长的可能前缀
                }
                temp /= 10;
            }
        }
        
        return maxLen;
    }
}

var longestCommonPrefix = function(arr1, arr2) {
    const prefixSet = new Set();
    
    // 将arr1中所有数的所有前缀存入集合
    for (let num of arr1) {
        while (num > 0) {
            prefixSet.add(num);
            num = Math.floor(num / 10);
        }
    }
    
    let maxLen = 0;
    
    // 检查arr2中每个数的前缀
    for (let num of arr2) {
        while (num > 0) {
            if (prefixSet.has(num)) {
                maxLen = Math.max(maxLen, num.toString().length);
                break; // 找到匹配后跳出，因为当前num是最长的可能前缀
            }
            num = Math.floor(num / 10);
        }
    }
    
    return maxLen;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度哈希表方法
时间复杂度O(n × d)
空间复杂度O(n × d)

其中：

  • n = max(len(arr1), len(arr2))
  • d = 平均数字位数（约为 log₁₀(max_value)）

对于约束条件 1 <= arr1[i], arr2[i] <= 10^8，最大位数为 8，所以复杂度实际上是线性的。

相关题目