a********e
发帖数: 53 | 1 class Solution {
public:
Write a function to find the longest common prefix string amongst an array
of strings.
The Time complexity is O(logM * N), while M is the size of strs, N is the
shortest length of the str in the strs
而我觉得这个时间复杂度应该是O(MN). 因为isEqual（）的复杂度应该是O(M), as T(M
) = 2T(M/2) + O(1). 谢谢。
============================
bool isEqual(vector &strs, int index, int start, int end) {
if(end < start) return true;
if(end == start) {
if(strs[start].size() > index) return true;
else return false;
}
int mid = (start + end) / 2;
bool lEqual = isEqual(strs, index, start, mid);
bool rEqual = isEqual(strs, index, mid + 1, end);
if(!lEqual || !rEqual) return false;
if(index > strs[start].size()) return false;
if(index > strs[end].size()) return false;
if(strs[start][index] != strs[end][index]) return false;
return true;
}
string longestCommonPrefix(vector &strs) {
// Note: The Solution object is instantiated only once and is reused by
each test case.
string res;
size_t vSize = strs.size();
if(0 == vSize) return res;
if(1 == vSize) return strs[0];
int len = 0;
while(isEqual(strs, len, 0, vSize - 1)) {
len ++;
}
res = strs[0].substr(0, len);
return res;
} |
|
