LeetCode 每日一题笔记

0. 前言

• 日期：2026.05.21
• 题目：3043. 最长公共前缀的长度
• 难度：中等
• 标签：数组、字典树（Trie）、哈希表

1. 题目理解

问题描述： 给定两个正整数数组 arr1 和 arr2，找出所有 (x,y) 数对（x 来自 arr1，y 来自 arr2）中，最长公共前缀的长度。如果不存在公共前缀，返回 0。

示例：

输入：arr1 = [1,10,100], arr2 = [1000] 输出：3 解释：(100, 1000) 的公共前缀是 100，长度为3，是所有数对中最长的。

2. 解题思路

核心观察

• 公共前缀的本质是数字高位的共同部分，因此可以用**字典树（Trie）**存储一个数组的所有数字前缀，再遍历另一个数组查询最长匹配长度；
• 也可以用哈希表存储 arr1 所有数字的前缀，再查询 arr2 的数字前缀是否存在，取最长长度。

算法步骤（哈希表法）

1. 遍历 arr1，将每个数字的所有前缀存入哈希表；
2. 遍历 arr2，对每个数字，依次取其前缀并检查是否在哈希表中；
3. 记录匹配到的最长前缀长度。

3. 代码实现

package lc3000_lc3099.lc3043;

import java.util.HashSet;

class Solution {
    public int longestCommonPrefix(int[] arr1, int[] arr2) {
        int res = 0;
        HashSet<Integer> set = new HashSet<>();
        for (int num : arr1) {
            while (num >= 10) {
                set.add(num);
                num /= 10;
            }
            set.add(num);
        }
        for (int num : arr2) {
            while (num >= 10) {
                if (set.contains(num)) {
                    res = Math.max(res, Integer.toString(num).length());
                }
                num /= 10;
            }
            if (set.contains(num)) {
                res = Math.max(res, 1);
            }
        }
        return res;
    }
}

4. 代码优化说明

减少冗余判断，统一处理单数字前缀的匹配逻辑，避免重复分支：

package lc3000_lc3099.lc3043;

import java.util.HashSet;

class Solution {
    public int longestCommonPrefix(int[] arr1, int[] arr2) {
        HashSet<Integer> set = new HashSet<>();
        for (int num : arr1) {
            int n = num;
            while (n > 0) {
                set.add(n);
                n /= 10;
            }
        }

        int maxLen = 0;
        for (int num : arr2) {
            int n = num;
            while (n > 0) {
                if (set.contains(n)) {
                    maxLen = Math.max(maxLen, String.valueOf(n).length());
                    break;
                }
                n /= 10;
            }
        }
        return maxLen;
    }
}

5. 复杂度分析

• 时间复杂度：$O(N\times D+M\times D)$，其中 $N$、$M$ 为两个数组长度，$D$ 为数字的最大位数（最多10位，可视为常数）。
• 空间复杂度：$O(N\times D)$，哈希表存储所有前缀的空间开销。

6. 总结

• 核心思路：前缀存储 + 匹配查询，哈希表法实现简单，字典树法在大数据下效率更高；
• 优化后代码统一了单数字前缀的处理逻辑，减少了冗余分支，可读性更强；
• 关键技巧：通过 num /= 10 循环剥离数字前缀，避免字符串转换的额外开销。