14. 最长公共前缀
难度简单编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀，返回空字符串 ""。
示例 1：
输入：strs = ["flower","flow","flight"] 输出："fl"
示例 2：
输入：strs = ["dog","racecar","car"] 输出："" 解释：输入不存在公共前缀。
class Solution {
public:
string longestCommonPrefix(vector<string>& strs) {
if (!strs.size()) {
return "";
}
string prefix = strs[0];
int count = strs.size();
for (int i = 1; i < count; ++i) {
prefix = longestCommonPrefix(prefix, strs[i]);
if (!prefix.size()) {
break;
}
}
return prefix;
}
string longestCommonPrefix(const string& str1, const string& str2) {
int length = min(str1.size(), str2.size());
int index = 0;
while (index < length && str1[index] == str2[index]) {
++index;
}
return str1.substr(0, index);
}
};
o(m*n)
其中 m是字符串数组中的字符串的平均长度，n 是字符串的数量。最坏情况下，字符串数组中的每个字符串的每个字符都会被比较一次。
其实就是暴力求解
复杂度o(m*n) m为最短字符串的长度 n为字符串的个数
长度为1 遍历一次
长度为2 遍历一次
长度为3 遍历一次
。。。。。
长度为最短字符串长度遍历一次
class Solution {
public:
string longestCommonPrefix(vector<string>& strs) {
if(!strs.size()){
return "";
}
int minL = getMinL(strs);
string pre = "";
bool flag = false;
for(int i =0; i< minL; i++){
for(int j = 0; j < strs.size(); j++){
if(strs[0].substr(0,i+1) != strs[j].substr(0,i+1)){
flag = true;
break;
}
}
if (flag){
break;
} else{
pre = strs[0].substr(0,i+1);
}
}
return pre;
}
int getMinL(vector<string>& strs){
int minL = pow(2,31) -1;
for (int i =0; i<strs.size(); i++){
if (minL > strs[i].length()){
minL = strs[i].length();
}
}
return minL;
}
};
s='abc'
s.substr(0,0) -> ''
s.substr(0,1) -> 'a'