最长公共前缀
编写一个函数来查找字符串数组中的最长公共前缀。如果不存在公共前缀,返回空字符串 ""。
示例 1:
输入: ["flower","flow","flight"]
输出: "fl"
示例 2:
输入: ["dog","racecar","car"]
输出: ""
解释: 输入不存在公共前缀。
说明:
所有输入只包含小写字母 a-z 。
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/longest-common-prefix
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
我就记录一下我的思路吧,没有特别复杂的技巧,特别的直,直来直去的。
思路:
让我们计算公共的前缀,那么我的思路就是从前2个元素开始干起,循环比较,计算出前2个公共的前缀(此时并不一定就是所有元素的公共前缀),我们从第2个元素开始,与公共前缀进行比较,如果不一样,就把公共前缀从不一样的地方直接截取掉(更新公共前缀为截取后的),循环后面的所有元素,并且不断的去更新前缀,循环结束,直接返回最后的前缀。
以下是代码实现,虽然繁碎,但是相信是比较容易理解的实现:
var longestCommonPrefix = function (strs) {
if (strs.length === 1) return strs[0]
let pre = ''
for (let i = 0; i < strs.length; i++) {
const curS = strs[i]
let j = 0
let z = 0
// 前2个的比较逻辑
if (i === 0) {
const nextS = strs[i + 1]
while (j < curS.length) {
if (curS[j] === nextS[j]) {
pre += curS[j]
}
j++
}
} else {
while (z < pre.length) {
// 此处多比较一次
if (pre[z] !== curS[z]) {
pre = pre.substring(0, z)
break
}
z++
}
}
}
return pre
}
网友评论