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;
}
};