LeetCode 3043. Find the Length of the Longest Common Prefix
原题链接
中等
作者:
_YH_YH_
,
2024-02-20 05:21:48
,
所有人可见
,
阅读 55
const int N = 1e6 + 10;
class Solution {
public:
int son[N][10], cnt[N], idx;
void insert(int x) {
int p = 0;
string c = to_string(x);
for (char digit : c) {
int u = digit - '0';
if (!son[p][u]) son[p][u] = ++idx;
p = son[p][u];
}
cnt[p]++;
}
int query(int x) {
int p = 0;
int maxv = 0;
string c = to_string(x);
for (char digit : c) {
int u = digit - '0';
if (!son[p][u]) return maxv;
p = son[p][u];
maxv++;
}
return maxv;
}
int longestCommonPrefix(vector<int>& arr1, vector<int>& arr2) {
for (auto& x : arr1)
insert(x);
int maxv = 0;
for (auto x : arr2)
maxv = max(maxv, query(x));
return maxv;
}
};