nineloong's blog

题目描述

LeetCode 3043 — 最长公共前缀的长度 (Medium)

给你两个正整数数组 arr1 和 arr2，请你返回 arr1 中任意元素与 arr2 中任意元素之间的最长公共前缀的长度。

公共前缀是指两个整数从高位开始，连续相同的数字位数。

示例 1：

输入：arr1 = [1,10,100], arr2 = [1000]
输出：3
解释：arr2 中的 1000 与 arr1 中的 100 的最长公共前缀是 "100"，长度为 3。

示例 2：

输入：arr1 = [1,2,3], arr2 = [4,5,6]
输出：0
解释：任意两个数之间都没有公共前缀。

约束：

1 <= arr1.length, arr2.length <= 5 * 10^4
1 <= arr1[i], arr2[i] <= 10^8

求解思路

最直接的想法是两层循环，把每对数字都转成字符串比一次前缀。但 arr1 和 arr2 各自最长可达 5 * 10^4， $O(n \times m)$ 的配对比较不可行。

换个角度看这个问题——我们要找的不是某两个特定元素的公共前缀，而是整个 arr2 中，谁能在 arr1 里找到最长的前缀匹配。也就是说，把 arr1 看成一个前缀集合，对 arr2 中每个元素查询它在这个集合里的最长匹配长度，最后取最大值。

这正好是字典树（Trie）的经典应用场景。数字转字符串之后，公共前缀就是字符从上往下一个一个比对——把 arr1 全部插入 Trie，相同前缀的数字自然共享同一条路径；然后拿 arr2 的每个数字去走树，能走多深，最长公共前缀就有多长。一旦某个字符的对应子节点为空，说明路径断了，后面的数字不可能再匹配，直接停就可以。

这题用 Trie 还有几个天然优势：数字字符集只有 0-9，每个节点分支固定为 10，结构紧凑；数字不超过 10^8，最多 9 位，树的深度很浅；而且只需要路径匹配，不需要像经典 Trie 那样设置结束标记，节点设计可以更简单。

解法：字典树

#include <vector>
#include <string>
using namespace std;

struct TrieNode {
    TrieNode* children[10];
    TrieNode() {
        for (int i = 0; i < 10; i++) {
            children[i] = nullptr;
        }
    }
};

class Trie {
private:
    TrieNode* root;

public:
    Trie() { root = new TrieNode(); }

    void insert(const string& word) {
        TrieNode* node = root;
        for (char ch : word) {
            int idx = ch - '0';
            if (node->children[idx] == nullptr) {
                node->children[idx] = new TrieNode();
            }
            node = node->children[idx];
        }
    }

    // 返回 word 与树中已有字符串的最长公共前缀长度
    int search(const string& word) {
        TrieNode* node = root;
        int depth = 0;
        for (char ch : word) {
            int idx = ch - '0';
            if (node->children[idx] != nullptr) {
                depth++;
                node = node->children[idx];
            } else {
                break; // 失配，后面的数字不可能匹配了
            }
        }
        return depth;
    }
};

class Solution {
public:
    int longestCommonPrefix(vector<int>& arr1, vector<int>& arr2) {
        Trie trie;
        for (int num : arr1) {
            trie.insert(to_string(num));
        }

        int maxLength = 0;
        for (int num : arr2) {
            int len = trie.search(to_string(num));
            maxLength = max(maxLength, len);
        }
        return maxLength;
    }
};

复杂度： 时间 $O((n + m) \cdot L)$ ， $L$ 为数字字符串长度（≤ 9），to_string 转换和 Trie 操作均在此范围内；空间 $O(n \cdot L)$ 。

变式：返回公共前缀本身

如果题目不只是要求长度，还要返回最长公共前缀字符串，只需在 search 中同步记录路径：

// 返回最长公共前缀字符串
string searchPrefix(const string& word) {
    TrieNode* node = root;
    string prefix;
    for (char ch : word) {
        int idx = ch - '0';
        if (node->children[idx] != nullptr) {
            prefix.push_back(ch);
            node = node->children[idx];
        } else {
            break;
        }
    }
    return prefix;
}

然后在 Solution 中比较字符串长度，保留最长的那一个即可。

每日一题：最长公共前缀的长度

题目描述

求解思路

解法：字典树

变式：返回公共前缀本身

相关题目