3043. 最长公共前缀的长度(Leetcode 每日一题)

3043. 最长公共前缀的长度 | 难度中等题目链接LeetCode 3043题意理解给定两个正整数数组arr1和arr2从arr1中选一个数x从arr2中选一个数y找出所有数对(x, y)中最长公共前缀的长度。前缀的定义一个整数的最左边一位或多位数字组成的整数。例如 123 是 12345 的前缀但 234 不是。用题目给的样例走一遍arr1 中的数arr2 中的数公共前缀长度110001110100010210010001003最长公共前缀是 100长度为3。关键观察两个数有公共前缀c等价于c既是x的前缀、又是y的前缀。比如 100 是 1000 的前缀也是 100 的前缀所以 100 是它们的公共前缀。解法思路核心想法把前缀匹配变成集合查重如果我们要判断两个数是否有公共前缀最直接的想法是把一个数的所有前缀都拿出来看另一个数的某个前缀是否也在其中。比如 1000 的所有前缀是 {1000, 100, 10, 1}100 的所有前缀是 {100, 10, 1}。取交集得到 {100, 10, 1}其中最长的就是 100。但逐对比较太慢了——arr1和arr2最多各 5×10⁴ 个元素两两配对就是 25 亿对。换个角度如果我们把arr1中所有数的所有前缀都存进一个集合然后遍历arr2中每个数的前缀看哪些能在集合里找到就能高效地解决问题遍历arr1对每个数逐次去掉末位num / 10把所有前缀存入unordered_set遍历arr2对每个数同样逐次去掉末位检查当前前缀是否在集合中出现过在所有匹配到的前缀中取最长的那个返回其长度为什么能想到用哈希集合因为问题本质是查重——判断 arr2 的某个前缀是否在 arr1 的前缀中出现过。哈希集合的查找是 O(1)天然适合这类问题。如何高效获取一个数的所有前缀一个正整数的所有前缀可以通过反复除以 10 取整得到num 12345 12345 → 1234 → 123 → 12 → 1 → 0停止每次num / 10就砍掉最后一位得到的就是一个前缀。这个过程的时间复杂度是 O(d)d 是数字的位数最多 9 位因为元素范围 ≤ 10⁸。一个小优化遍历arr2中的数时我们是从大到小检查前缀的先检查完整的数再去掉末位。所以一旦发现某个前缀在集合中它一定是当前数能匹配到的最长公共前缀可以直接 break不必继续往更短的前缀查。代码实现理解了上面的思路代码就很好写了classSolution{public:intlongestCommonPrefix(vectorintarr1,vectorintarr2){// 第一步把 arr1 中所有数的所有前缀存入哈希集合unordered_setintprefixes;for(intnum:arr1){while(num0){prefixes.insert(num);// 当前数本身就是自己的一个前缀num/10;// 砍掉末位得到更短的前缀}}// 第二步遍历 arr2对每个数从长到短检查前缀intmaxPrefix0;for(intnum:arr2){while(num0){if(prefixes.count(num)){// 从长到短检查第一个匹配的一定是最长公共前缀maxPrefixmax(maxPrefix,num);break;// 不必再查更短的前缀}num/10;// 砍掉末位试下一个更短的前缀}}// 第三步将最长的公共前缀转为字符串取其长度if(maxPrefix0)return0;returnto_string(maxPrefix).size();}};复杂度分析时间复杂度O(U₁ × D U₂ × D)其中 U₁、U₂ 是 arr1、arr2 中不同前缀的数量最坏各 5×10⁴ × 9D 是数字最大位数≤ 9。实际运行很快因为每个数的位数有限。空间复杂度O(U₁ × D)哈希集合存储 arr1 的所有前缀。关于前缀树Trie解法这道题也可以用前缀树来做把 arr1 的所有数按位插入 Trie然后对 arr2 中的每个数沿 Trie 往下走走到的最大深度就是最长公共前缀的长度。思路是对的但实现上更复杂——你需要把整数拆成逐位数字还要维护节点和计数。对于这道题来说哈希集合已经足够简洁高效Trie 更适合需要支持前缀查询更复杂操作的场景比如动态插入删除、统计前缀数量等。如果只是查是否存在哈希集合是更直觉、更简单的选择。下面给出 Trie 解法的代码供参考可以看到和哈希集合解法相比实现明显更重classSolution{public:// Trie 节点children[0~9] 对应数字 0~9structTrieNode{TrieNode*children[10];TrieNode(){fill(children,children10,nullptr);}};intlongestCommonPrefix(vectorintarr1,vectorintarr2){TrieNode*rootnewTrieNode();// 把 arr1 中的数按位插入 Triefor(intnum:arr1){// 先把数字拆成逐位数字高位在前vectorintdigits;inttempnum;while(temp0){digits.push_back(temp%10);temp/10;}reverse(digits.begin(),digits.end());// 逐位插入TrieNode*noderoot;for(intd:digits){if(!node-children[d])node-children[d]newTrieNode();nodenode-children[d];}}// 对 arr2 中的数沿 Trie 走记录最大深度intres0;for(intnum:arr2){vectorintdigits;inttempnum;while(temp0){digits.push_back(temp%10);temp/10;}reverse(digits.begin(),digits.end());TrieNode*noderoot;intdepth0;for(intd:digits){if(!node-children[d])break;// 走不通了停止nodenode-children[d];depth;}resmax(res,depth);}returnres;}};可以看到Trie 解法需要额外定义节点结构、手动拆位和建树代码量明显多于哈希集合解法。两种方法的时间复杂度同级但哈希集合的实现更简洁直观。易错点忘记num / 10时 num 为 0 要停止。如果 while 条件写成while (num 0)而不是while (num 0)0 会死循环。从 arr2 的数检查前缀时忘记从大到小检查。如果从小到大检查先查 1 位数前缀即使匹配了也不能 break还得继续查更长的前缀逻辑反而更复杂。从大到小查匹配即可 break更高效也更简洁。相关题目14. 最长公共前缀字符串版的最长公共前缀思路类似但操作对象是字符串208. 实现 Trie (前缀树)理解前缀树的标准实现适合想深入学习 Trie 的读者总结这道题的核心是把**两个数的最长公共前缀转化为集合查重问题**一个数的所有前缀可以通过num / 10逐次砍末位得到无需转字符串把 arr1 的所有前缀存入哈希集合再对 arr2 的每个数从长到短查匹配即可 breakTrie 也能做但实现更重适合需要复杂前缀操作的场景一句话当问题可以归结为是否存在时优先考虑哈希集合而非更重的数据结构。