3043.
longest common prefix
数字好多
懒得思考直接开trie==
感觉也可以直接用lca那套
还是等等用BIT试试
class Trie{
public:
vector<Trie*> num;
Trie(){
num = vector<Trie*>(10, nullptr);
}
};
class Solution {
public:
Trie* root = new Trie();
int longestCommonPrefix(vector<int>& arr1, vector<int>& arr2) {
for(int& i: arr1){
Trie* t = root;
string s = to_string(i);
for(char& c: s){
int idx = c - '0';
if(t->num[idx] == nullptr)
t->num[idx] = new Trie();
t = t->num[idx];
}
}
int maxlen = 0;
for(int& i: arr2){
Trie* t = root;
string s = to_string(i);
int curlen = 0;
for(char& c: s){
int idx = c - '0';
if(t->num[idx] == nullptr) break;
curlen++;
t = t->num[idx];
}
maxlen = max(maxlen, curlen);
}
return maxlen;
}
};

不对 完全没必要 他又没要找lca==感觉还是trie一下就好