Open GleanCoder1116 opened 4 years ago
题目中有两个关键字;公共和前缀;通过这两个方面进行分析解答;首先是公共 即在说给定的选项中都含有某个特定的连续字符串;另外关键点就是前缀;首先就是从第0位开始的到某一位结束的特殊字符串 根据以上个人的理解 自己给出了以下答案
/**
* @param {string[]} strs
* @return {string}
*/
const longestCommonPrefix = (strs = []) => {
// 如果传入的值是空数组直接return '' 做个简单的优化
if (strs.length === 0) {
return ''
}
// 获取长度最小的 str 为基准值 以它开始遍历;这样能够减少循环的次数
let minStr = strs[0]
let prefixStrs = ''
strs.forEach((str, index) => {
if (minStr.length > str) {
minStr = str
minStrIndex = index
}
})
minStr = minStr ? [...minStr] : []
// 对最小值进行遍历
let isEnd = false // 如果在某一项发现不再相等 就直接停止循环并输出结果
for (let index = 0; index < minStr.length; index++) {
const char = minStr[index]
const isCommon = strs.every(str => {
if (str[index] !== char) {
isEnd = true
return false
}
return str[index] === char
})
// 如果出现某一位不相等的话直接就结束循环
if (isEnd) {
break
}
isCommon && (prefixStrs = prefixStrs + char)
}
return prefixStrs
}
解题思路:
获取数组中的最大值及最小值字符串,最小字符串与最大字符串的最长公共前缀也为其他字符串的公共前缀,即为字符串数组的最长公共前缀
例如 abc 、 abcd 、ab 、ac ,最小 ab 与最大 ac 的最长公共前缀一定也是 abc 、 abcd 的公共前缀
var longestCommonPrefix = function (strs) {
if (strs === null || strs.length === 0) return ''
if (strs.length === 1) return strs[0]
// 最大值和最小值下标
let min = 0
let max = 0
// 找到最大、最小值的下标
for (let i = 1; i < strs.length; i++) {
if (strs[min] > strs[i]) min = i
if (strs[max] < strs[i]) max = i
}
for (let j = 0; j < strs[min].length; j++) {
if (strs[min].charAt(j) !== strs[max].charAt(j)) {
return strs[min].substring(0, j)
}
}
return strs[min]
}
示例1
示例2
说明
所有输入只包含小写字母
a-z