0产出的一天 明天meeting gg
题目: 3043. Find the Length of the Longest Common Prefix
给你两个int vector: arr1, arr2求出arr1中的整数在arr2中整数最长的prefix len
思路:
先用arr2中的数字做trie，然后拿arr1中的整数一个个下去扫prefix len每次确定需不
需要更新最大值，利用转成字串再一个个digit下去做overall复杂度是arr1和arr2中的
digit数总和，排名前面的做法虽然复杂度一样但是几乎都是直接用整数的乘除操作完成
感觉直接用整数operator下去做会比转成字串这个行为快?
class trie{
public:
vector<trie*> t;
trie(){
t=vector<trie*>(10,nullptr);
}
};
class Solution {
public:
int longestCommonPrefix(vector<int>& arr1, vector<int>& arr2) {
trie* pre_ans= new trie();
int ans=0;
for(auto k:arr2){
trie* temp=pre_ans;
string s=to_string(k);
for(auto j:s){
if(!temp->t[j-'0']){
temp->t[j-'0']=new trie();
}
temp=temp->t[j-'0'];
}
}
for(auto k:arr1){
string s=to_string(k);
trie* temp=pre_ans;
int cur=0;
for(auto g:s){
if(!temp->t[g-'0']){
break;
}
else{
cur++;
temp=temp->t[g-'0'];
}
}
ans=max(cur,ans);
}
return ans;
}