14. 最长公共前缀

1. 题目描述

编写一个函数来查找字符串数组中的最长公共前缀。

如果不存在公共前缀，返回空字符串 “”。

示例 1:

输入: ["flower","flow","flight"]
输出: "fl"

示例 2:

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

说明：所有输入只包含小写字母 a-z 。

2. 解题思路

可以使用递归来实现：

• 获取第一个字符串，作为最长公共前缀存在变量中
• 从数组中取出下一个字符串，与当前最长公共前缀对比，得到新的最长公共前缀，并储存在变量中
• 重复第二步，直到遍历完整个数组

还可以使用迭代来实现：

• 先假设最长公共前缀长度为1，存到变量i中。从第一个字符串中取出第i个字符与数组其他字符串的第i个字符进行对比，如果都一样，那么最长公共前缀长度加一
• 重复第一步的操作，直到flag为false，或者i和第一个字符串长度相等时

• 返回第一个字符串的前i个字符

  3. 代码实现

  递归实现：

  /**
  * @param {string[]} strs
  * @return {string}
  */
  var longestCommonPrefix = function(strs) {
   function findCommonPrefix(a,b){
      let i = 0
      while(i<a.length && i<b.length && a.charAt(i)===b.charAt(i)){
          i++
      }
      return i>0 ?a.substring(0,i) : ''
   }
   if(strs.length>0){
       let commonPrefix = strs[0]
       for(let i = 0; i<strs.length; i++){
           commonPrefix = findCommonPrefix(commonPrefix, strs[i])
       }
       return commonPrefix
   }
   return ''
  };

  迭代实现：

  /**
  * @param {string[]} strs
  * @return {string}
  */
  var longestCommonPrefix = function(strs) {
   if(strs.length===0){
       return ''
   }
   let i = 0
   let flag = true
   while(flag){
       if(strs[0].length>i){
           const char = strs[0].charAt(i)
           for(let j = 1; j<strs.length; j++){
               if(strs[j].length <= i || strs[j].charAt(i)!==char){
                   flag = false
                   break
               }
           }
       }else{
           flag = false
       }
       i++
   }
   return strs[0].substring(0, i-1)
  };

  4. 提交结果

  递归实现：
  
  迭代实现：