14. 最长公共前缀

https://leetcode-cn.com/problems/longest-common-prefix/

原题

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

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

示例 1:
输入: [“flower”,”flow”,”flight”]
输出: “fl”

示例 2:
输入: [“dog”,”racecar”,”car”]
输出: “”

解释: 输入不存在公共前缀。
说明: 所有输入只包含小写字母 a-z 。

题目分析

确定一下题意，前缀是指从头开始的字符串，公共是指数组中的所有字符串都需要有的字符串。
最直观的方法是，设置最长前缀为数组第一个元素，然后遍历数组依次比较当前的最长前缀和当前元素，然后更新最长前缀继续与下一个元素比较。

const longestCommonPrefixStr = (str1, str2) => {
  let ans = ''
  for (let i = 0; i < Math.min(str1.length, str2.length); i++) {
    if (str1[i] === str2[i]) {
      ans += str1[i]
    } else {
      return ans
    }
  }
  return ans
}
const longestCommonPrefix = (strs) => {
  if (!strs.length) return ''
  let ans = strs[0]
  for (let i = 1; i < strs.length; i++) {
    ans = longestCommonPrefixStr(ans, strs[i])
  }
  return ans
}

既然是公共前缀，那我们可以找一个公共前缀的基准例如数组的第一个元素，遍历其他数组，如果其他数组都含有这个前缀，则这个公共前缀为最长的公共前缀。如果其他元素没有这个前缀，则更新公共前缀的长度-1，再去数组中匹配，直到找到所有数组都含有的前缀。

const longestCommonPrefix = (strs) => {
    if (!strs.length) return ''
    let ans = strs[0]
    for (let i = 0; i < strs[0].length; i++) {
        let has = true
        for (let j = 1; j < strs.length; j++) {
            if (strs[j].indexOf(ans) === -1) {
                has = false
                break
            }
        }
        if (has) {
            break
        } else {
            ans = ans.slice(0, ans.length - i - 1)
        }
    }
    return ans
}