1 min read
https://leetcode.com/problems/longest-common-prefix/
Divide and conquer, compare left and right subarrays.
class Solution {
string lcp(vector<string> &strs, int l, int r) {
if (l == r)
return strs[l];
else {
int mid = l + (r - l) / 2;
string leftLCP = lcp(strs, l, mid);
string rightLCP = lcp(strs, mid + 1, r);
return commonPrefix(leftLCP, rightLCP);
}
}
string commonPrefix(string left, string right) {
int l = min(left.length(), right.length());
int ctr = 0;
while (ctr < l && left[ctr] == right[ctr]) {
ctr++;
}
return left.substr(0, ctr);
}
public:
string longestCommonPrefix(vector<string> &strs) {
if (strs.size() < 0)
return "";
return lcp(strs, 0, strs.size() - 1);
}
};