LeetCode偶尔一题 —— 14. 最长公共前缀

原题地址:https://leetcode-cn.com/problems/longest-common-prefix/

题目描述

分析题目

对于这道题最直观的感觉就是:

  • 找到第一个字符串 target
  • 进行按列的水平扫描

我的代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
* @param {string[]} strs
* @return {string}
*/
var longestCommonPrefix = function(strs) {
if (!strs || !strs.length) {
return ''
}
let target = strs[0]
for (let i = 0; i < target.length; i++) {
for (let j = 1; j < strs.length; j++) {
if (strs[j][i] !== target[i]) {
return i > 0 ? target.slice(0, i) : ''
}
}
}
return target
};
  • 时间复杂度:O(s)s = m + n(s就是总的字符串的长度)
  • 空间复杂度:O(1)

当然,这道题还有其他解法,比如二分法、分治法,官方题解 已经写得非常细致了,这里就不重复写了。