Description
Write a function to find the longest common prefix string amongst an array of strings.
思路
- 最长的公共前缀，所以，先找出前两个的最长前缀，然后再和后面的比，在比的过程中，记录最小的串的长度，很明显，最长的前缀肯定会小于等于最小串的。算是一个丁点儿优化吧
代码
class Solution {
public:
string longestCommonPrefix(vector<string>& strs) {
string res;
int len = strs.size();
if(len == 0) return res;
if(len == 1) return strs[0];
string prefix;
int i = 0, j = 0;
for(; i < strs[0].size() && j < strs[1].size();){
if(strs[0][i] == strs[1][j]){
prefix += strs[0][i];
i++;
j++;
}
else break;
}
int min_len = 0;
for(i = 2; i < len; ++i){
min_len = min(strs[i].size(), prefix.size());
if(min_len == 0) return "";
for(j = 0; j < min_len; ++j){
if(strs[i][j] != prefix[j])
break;
}
prefix = prefix.substr(0, j);
}
return prefix;
}
};内容来源于网络如有侵权请私信删除
- 还没有人评论，欢迎说说您的想法！
客服
