题目描述
给你两个 正整数 数组 arr1
和 arr2
。
正整数的 前缀 是其 最左边 的一位或多位数字组成的整数。例如,123
是整数 12345
的前缀,而 234
不是。
设若整数 c
是整数 a
和 b
的 公共前缀,那么 c
需要同时是 a
和 b
的前缀。例如,5655359
和 56554
有公共前缀 565
,而 1223
和 43456
没有 公共前缀。
你需要找出属于 arr1
的整数 x
和属于 arr2
的整数 y
组成的所有数对 (x, y)
之中最长的公共前缀的长度。
返回所有数对之中最长公共前缀的长度。如果它们之间不存在公共前缀,则返回 0
。
样例
输入:arr1 = [1,10,100], arr2 = [1000]
输出:3
解释:存在 3 个数对 (arr1[i], arr2[j]):
- (1, 1000) 的最长公共前缀是 1。
- (10, 1000) 的最长公共前缀是 10。
- (100, 1000) 的最长公共前缀是 100。
最长的公共前缀是 100,长度为 3。
输入: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
算法
(字典树) $O(n \log m |\Sigma|)$
- 将
arr1
中的所有数字插入到一棵字典树中。 - 遍历
arr2
的每个数字,在字典树中匹配前缀,返回最长的匹配长度。
时间复杂度
- 字典树一共有 $O(n \log m |\Sigma|)$ 个节点。
- 每次匹配的时间复杂度为 $O(\log m)$。
- 故总时间复杂度为 $O(n \log m |\Sigma|)$。
空间复杂度
- 需要 $O(n \log m |\Sigma|)$ 的额外空间存储字典树。
C++ 代码
struct Node {
Node *nxt[10];
Node() {
memset(nxt, 0, sizeof(nxt));
}
};
class Solution {
private:
Node *r;
void insert(int x) {
string s = to_string(x);
Node *p = r;
for (char c : s) {
if (p->nxt[c - '0'] == NULL)
p->nxt[c - '0'] = new Node();
p = p->nxt[c - '0'];
}
}
int query(int x) {
string s = to_string(x);
Node *p = r;
int res = 0;
for (char c : s) {
if (p->nxt[c - '0'] == NULL)
break;
++res;
p = p->nxt[c - '0'];
}
return res;
}
public:
int longestCommonPrefix(vector<int>& arr1, vector<int>& arr2) {
r = new Node();
for (int x : arr1)
insert(x);
int ans = 0;
for (int x : arr2)
ans = max(ans, query(x));
return ans;
}
};