※ 引述《sixB (6B)》之铭言：
: 标题: Re: [闲聊] 每日leetcode
: 时间: Tue Sep 24 09:04:47 2024
:
: 3043.
:
: longest common prefix
刚刚写完了
第一次是直接比较
发现TLE了
class Solution {
public:
int longestCommonPrefix(vector<int>& arr1, vector<int>& arr2) {
int longest_prefix = INT_MIN;
cout << arr1.size() << "\n";
set(arr1.begin(), arr1.end());
set(arr2.begin(), arr2.end());
cout << arr1.size() << "\n";
for(int i : arr1){
for(int j : arr2){
int tmp_l = compare_prefix(i, j);
if(tmp_l > longest_prefix){
longest_prefix = tmp_l;
}
}
}
return longest_prefix;
}
int compare_prefix(int a, int b){
string a_s = to_string(a);
string b_s = to_string(b);
int longest_prefix = 0;
for(int i = 0 ; i < a_s.size() ; i++){
if(a_s[i] != b_s[i]){
break;
}
longest_prefix ++;
}
return longest_prefix;
}
};
因为不会用Trie就去看了一下可以用Hash
用了就过了
我先用Hash存arr1的全部prefix
跟我上面的写法时间复杂度有差这么多喔
原本以为差不多