14. 最长公共前缀
题目
编写一个函数来查找字符串数组中的最长公共前缀。如果不存在公共前缀，返回空字符串 ""。
示例1：
输入：strs = ["flower","flow","flight"]
输出："fl"
示例2：
输入：strs = ["dog","racecar","car"]
输出：""
解释：输入不存在公共前缀。
解题思路
- 横向比较
class Solution {
public:
string longestCommonPrefix(vector& strs) {
if (!strs.size()||strs[0]=="") {//如果vector里没有东西
return "";
}
string prefix=strs[0];//以strs[0]为标准
int count=strs.size();//容器的容量
//对容器里的字符串逐个与prefix即strs[0]比较，得出最大相同的子串，在这个过程中显然prefix是逐步更新的
for(int i=1;i - 纵向比较
class Solution {
public:
string longestCommonPrefix(vector& strs) {
if (!strs.size()||strs[0]=="")return "";
int length=strs[0].size(); //容器里第一个字符串的长度
int count=strs.size(); //容器里有多少字符串
for(int i=0;i - 分治法
class Solution {
public:
string longestCommonPrefix(vector& strs) {
if (!strs.size()) {
return "";
}
else {
return longestCommonPrefix(strs, 0, strs.size() - 1);
}
}
string longestCommonPrefix(const vector& strs, int start, int end) {
if (start == end) {
return strs[start];
}
else {
int mid = (start + end) / 2;
string lcpLeft = longestCommonPrefix(strs, start, mid);
string lcpRight = longestCommonPrefix(strs, mid + 1, end);
return commonPrefix(lcpLeft, lcpRight);
}
}
string commonPrefix(const string& lcpLeft, const string& lcpRight) {
int minLength = min(lcpLeft.size(), lcpRight.size());
for (int i = 0; i < minLength; ++i) {
if (lcpLeft[i] != lcpRight[i]) {
return lcpLeft.substr(0, i);
}
}
return lcpLeft.substr(0, minLength);
}
};
- 先排序再比较
class Solution {
public:
string longestCommonPrefix(vector& strs) {
sort(strs.begin(), strs.end());
string ans;
string fir = strs.front();
string last = strs.back();
for(int i = 0; i