最长公共前缀

发表于 | 分类于 |
字数统计: 304 字 | 阅读时长 ≈ 1 分钟

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

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

示例 1：
输入：strs = [“flower”,”flow”,”flight”]
输出：”fl”

示例 2：
输入：strs = [“dog”,”racecar”,”car”]
输出：””
解释：输入不存在公共前缀。

纵向扫描

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

1
2
3
4
5
6
7
8
9
10
11
12
var longestCommonPrefix = function(strs) {
  let len = strs[0].length
  let count = strs.length
  for(let i = 0; i < len; i++) {
    for(let j = 1; j < count; j++) {
      if(i === strs[j].length || strs[0][i] !== strs[j][i]) {
        return strs[0].slice(0, i)
      }
    }
  }
  return strs[0]
};

复杂度分析

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