最长公共前缀

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

示例

示例 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)。使用的额外空间复杂度为常数。