※ 引述《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
跟我上面的寫法時間複雜度有差這麼多喔
原本以為差不多