Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
class Solution {
public:
string longestCommonPrefix(vector<string>& strs) {
int len_s = strs.size();
if(len_s == 0) return "";
return longestCommonPrefix(strs, 0, len_s - 1);
}
string longestCommonPrefix(vector<string>& strs, int l, int r){
if(l == r){
return strs[l];
}
else{
int mid = (l + r)/2;
string l_part = longestCommonPrefix(strs, l, mid);
string r_part = longestCommonPrefix(strs, mid+1, r);
return calculateCommonPrefix(l_part, r_part);
}
}
string calculateCommonPrefix(string& l, string& r){
int minLen = min(l.size(), r.size());
for(int i = 0; i < minLen; i++){
if(l[i] != r[i])
return l.substr(0, i);
}
return l.substr(0, minLen);
}
};
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment