编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀,返回空字符串 ""。
示例
输入: ["flower","flow","flight"]
输出: "fl"
输入: ["dog","racecar","car"]
输出: ""
解释: 输入不存在公共前缀。
说明
所有输入只包含小写字母 a-z 。
抛砖引玉
/**
* @param {string[]} strs
* @return {string}
*/
var longestCommonPrefix = function (strs) {
if (!strs.length) return ''
let _resultNum = strs[0].length - 1
for (let i = 1; i < strs.length; i++) {
while (
strs[i - 1].substring(0, _resultNum + 1) !==
strs[i].substring(0, _resultNum + 1)
) {
_resultNum--
}
}
return strs[0].substring(0, _resultNum + 1) || ''
}
官方答案
横向扫描
/**
* @param {string[]} strs
* @return {string}
*/
var longestCommonPrefix = function (strs) {
if (strs == null || strs.length == 0) {
return ''
}
var prefix = strs[0]
var count = strs.length
for (var i = 1; i < count; i++) {
prefix = CommonPrefix(String(prefix), String(strs[i]))
if (prefix.length == 0) {
break
}
}
return prefix
function CommonPrefix(str1, str2) {
var length = Math.min(str1.length, str2.length)
var index = 0
while (index < length && str1.charAt(index) == str2.charAt(index)) {
index++
}
return str1.substring(0, index)
}
}
纵向扫描
从前往后遍历所有字符串的每一列,比较相同列上的字符是否相同,
/**
* @param {string[]} strs
* @return {string}
*/
var longestCommonPrefix = function (strs) {
if (strs == null || strs.length == 0) {
return ''
}
var length = String(strs[0]).length
var count = strs.length
for (var i = 0; i < length; i++) {
var c = strs[0].charAt(i)
for (var j = 1; j < count; j++) {
if (i == strs[j].length || strs[j].charAt(i) != c) {
return strs[0].substring(0, i)
}
}
}
return strs[0]
}
其他解法
re 初始化为数组中第一个元素,逐个比较,当比较通过时返回 re,否则削去末位直至比较通过
/**
* @param {string[]} strs
* @return {string}
*/
var longestCommonPrefix = function (strs) {
var re = strs[0] ? strs[0] : ''
for (var i = 1; i < strs.length; i++) {
var regex = new RegExp('^' + re)
while (!regex.test(strs[i]) && re.length) {
re = re.slice(0, re.length - 1)
regex = new RegExp('^' + re)
}
}
return re
}