编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀，返回空字符串 ""。
示例
示例 1：
- 输入：strs = ["flower","flow","flight"]
- 输出："fl"
示例 2：
- 输入：strs = ["dog","racecar","car"]
- 输出：""
解答
方法一：横向扫描
依次遍历字符串数组中的每个字符串，对于每个遍历到的字符串，更新最长公共前缀，当遍历完所有的字符串以后，即可得到字符串数组中的最长公共前缀。如果中间发现比较出来的字符串长度为0，就可以退出循环。
用LCP(S1…Sn) 表示字符串 S1…S n的最长公共前缀。
可以得到以下结论：
LCP(S1…Sn)=LCP(LCP(LCP(S1,S2),S3),…Sn)
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
/**
* @param {string[]} strs
* @return {string}
*/
var longestCommonPrefix = function(strs) {
if(strs.length == 0){
return ""
}else if(strs.length == 1){
return strs[0]
}else{
let result = strs[0];
for(let i = 1;i<strs.length;i++){
result = compare(result,strs[i]);//逐次比较
if(result.length == 0){
result = ""
break;
}
}
return result;
}
};
/**
* @param {string} str1
* @param {string} str2
* @return {string}
*/
function compare(str1,str2){
let length = str1.length>str2.length?str2.length:str1.length;//选取最短的进行计算
let result = '';
for(let i =0;i<length;i++){
if(str2.substring(0,i+1) != str1.substring(0,i+1)){//有不相等即退出
break;
}else{
result = str2.substring(0,i+1);
}
}
return result;
}
复杂度分析
- 时间复杂度：O(mn)，其中 m 是字符串数组中的字符串的平均长度，n 是字符串的数量。最坏情况下，字符串数组中的每个字符串的每个字符都会被比较一次。
- 空间复杂度：O(1)。使用的额外空间复杂度为常数。
方法二：纵向扫描
纵向扫描时，从前往后遍历所有字符串的每一列，比较相同列上的字符是否相同，如果相同则继续对下一列进行比较，如果不相同则当前列不再属于公共前缀，当前列之前的部分为最长公共前缀。没经过训练的第一想法就是这个
/**
* @param {string[]} strs
* @return {string}
*/
var longestCommonPrefix = function(strs) {
if(strs.length == 0){
return ""
}else if(strs.length == 1){
return strs[0]
}else{
let result = "";
let flag = true;//是否存在不匹配的场景
for(let i = 0;i<strs[0].length;i++){//拿第一个为基数进行比较
let temp = strs[0].substring(0,i+1);
for(let j = 1;j<strs.length;j++){//每次都遍历整个数组
if(temp!=strs[j].substring(0,i+1)){//出现不匹配即退出
flag = false;
break;
}
}
if(!flag){
result = strs[0].substring(0,i);
break;
}else{
result = temp;
}
}
return result;
}
};
复杂度分析
- 时间复杂度：O(mn)，其中 m 是字符串数组中的字符串的平均长度，n 是字符串的数量。最坏情况下，字符串数组中的每个字符串的每个字符都会被比较一次。
- 空间复杂度：O(1)。使用的额外空间复杂度为常数。
