前缀题库

题一、最长公共前缀

---

编写一个函数来查找字符串数组中的最长公共前缀。如果不存在公共前缀，返回空字符串 ""。

示例1:

输入：strs = ["flower","flow","flight"]
输出："fl"

示例2:

输入：strs = ["dog","racecar","car"]
输出：""
解释：输入不存在公共前缀。

方案A、横向扫描

思路: 用 LCP(S1…Sn) 表示字符串 S1…Sn 的最长公共前缀。可以得到以下结论: LCP(S1…Sn)=LCP(LCP(LCP(S1,S2),S3),…Sn)

• 初始默认 strs[0] 为最长公共前缀，即 prefix=strs[0]
• 从第二个字符串开始，依次与 prefix 比较得出相同的公共前缀，更新 prefix(字符串两两比较)

function longestCommonPrefix(strs){
    const {length} = strs;
    let prefix = strs[0];
    for(let i=0;i<length;i++){
        let minLen = Math.min(prefix.length,strs[i].length);
        let index = 0;
        while(index < minLen && prefix[index] === strs[i][index]){
            index++;
        }
        prefix = prefix.substring(0,index);
        if(prefix.length === 0){
            return ""
        }
    }
    return prefix;
}

性能分析:

时间复杂度：O(mn)，其中 mm 是字符串数组中的字符串的平均长度，n 是字符串的数量。最坏情况下，字符串数组中的每个字符串的每个字符都会被比较一次。

空间复杂度：O(1)。使用的额外空间复杂度为常数。

方案B、纵向扫描

思路: 纵向扫描时，从前往后遍历所有字符串的每一列，比较相同列上的字符是否相同，如果相同则继续对下一列进行比较，如果不相同则当前列不再属于公共前缀，当前列之前的部分为最长公共前缀。

• 初始默认 strs[0] 为最长公共前缀，即 prefix=strs[0]
• prefix 中的每一个字符与 strs 中剩下的字符串的每一个字符进行比较，当遍历完成或者有一个字符不相同时，返回截取后的 prefix（字符串中的每一个字符两两比较）

function longestCommonPrefix(strs){
   if(strs == null || strs.length === 0){
    return ""
   }
   const {length} = strs;
   const {length:length0} = strs[0];
   for(let i=0;i<length0;i++){
    let char = strs[0][i];
    for(let j=1;j<length;j++){
        if(i === strs[j].length || strs[j][i] !== char){
            return strs[0].substring(0,i);
        }
    }
   }
   return strs[0]
}

性能分析:

时间复杂度：O(mn)，其中 m 是字符串数组中的字符串的平均长度，n 是字符串的数量。最坏情况下，字符串数组中的每个字符串的每个字符都会被比较一次。

空间复杂度：O(1)。使用的额外空间复杂度为常数。