編寫一個(gè)函數(shù)來查找字符串?dāng)?shù)組中的最長公共前綴。
如果不存在公共前綴呻惕，返回空字符串 ""滥比。
示例
示例 1：
- 輸入：strs = ["flower","flow","flight"]
- 輸出："fl"
示例 2：
- 輸入：strs = ["dog","racecar","car"]
- 輸出：""
解答
方法一：橫向掃描
依次遍歷字符串?dāng)?shù)組中的每個(gè)字符串，對(duì)于每個(gè)遍歷到的字符串型酥，更新最長公共前綴查乒，當(dāng)遍歷完所有的字符串以后玛迄，即可得到字符串?dāng)?shù)組中的最長公共前綴。如果中間發(fā)現(xiàn)比較出來的字符串長度為0蓖议，就可以退出循環(huán)。
用LCP(S1…Sn) 表示字符串 S1…S n的最長公共前綴纺阔。
可以得到以下結(jié)論：
LCP(S1…Sn)=LCP(LCP(LCP(S1,S2),S3),…Sn)
著作權(quán)歸作者所有修然。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系作者獲得授權(quán)愕宋，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處。
/**
* @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;//選取最短的進(jìn)行計(jì)算
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;
}
復(fù)雜度分析
- 時(shí)間復(fù)雜度：O(mn)，其中 m 是字符串?dāng)?shù)組中的字符串的平均長度蝎土，n 是字符串的數(shù)量。最壞情況下誊涯，字符串?dāng)?shù)組中的每個(gè)字符串的每個(gè)字符都會(huì)被比較一次醋拧。
- 空間復(fù)雜度：O(1)。使用的額外空間復(fù)雜度為常數(shù)丹壕。
方法二：縱向掃描
縱向掃描時(shí)庆械，從前往后遍歷所有字符串的每一列，比較相同列上的字符是否相同菌赖，如果相同則繼續(xù)對(duì)下一列進(jìn)行比較缭乘，如果不相同則當(dāng)前列不再屬于公共前綴，當(dāng)前列之前的部分為最長公共前綴琉用。沒經(jīng)過訓(xùn)練的第一想法就是這個(gè)
/**
* @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;//是否存在不匹配的場(chǎng)景
for(let i = 0;i<strs[0].length;i++){//拿第一個(gè)為基數(shù)進(jìn)行比較
let temp = strs[0].substring(0,i+1);
for(let j = 1;j<strs.length;j++){//每次都遍歷整個(gè)數(shù)組
if(temp!=strs[j].substring(0,i+1)){//出現(xiàn)不匹配即退出
flag = false;
break;
}
}
if(!flag){
result = strs[0].substring(0,i);
break;
}else{
result = temp;
}
}
return result;
}
};
復(fù)雜度分析
- 時(shí)間復(fù)雜度：O(mn)堕绩，其中 m 是字符串?dāng)?shù)組中的字符串的平均長度，n 是字符串的數(shù)量邑时。最壞情況下奴紧，字符串?dāng)?shù)組中的每個(gè)字符串的每個(gè)字符都會(huì)被比較一次。
- 空間復(fù)雜度：O(1)晶丘。使用的額外空間復(fù)雜度為常數(shù)。
