Leetcode 14 最长公共前缀
文章目录
编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀,返回空字符串 "" 。
示例 1:
输入:strs = ["flower","flow","flight"]
输出:"fl"
示例 2:
输入:strs = ["dog","racecar","car"]
输出:""
解释:输入不存在公共前缀。
解题思路
第一种解法是逐个比较,先比较第一和第二个字符串的最长公共前缀,然后再用这个前缀和第三个字符串比较,以此类推。
function longestCommonPrefix(strs) {
return strs.reduce((accu, cur) => {
let prefix = "";
for (let i = 0; i < accu.length; i++) {
if (accu[i] === cur[i]) {
prefix += accu[i];
} else {
return prefix;
}
}
return prefix;
})
}使用reduce如果没有指定初始值,一定要确保数组非空,由于这道题已经说明了strs长度大于等于 1 ,所以不用对空值进行处理
时间复杂度:O(s),s是所有字符串中字符数量的总和
空间复杂度:O(1)
上面这种方法思路很容易想到,但是需要进行大量的遍历操作,时间复杂度较高。第二种方法是仅比较最大、最小字符串的最长公共前缀。这里说的最大、最小指的是 ACSII 编码的先后顺序,例如 ab 小于 abc ,abc 小于 abcd ,abcd 小于 ac ,那么最小 ab 与最大 ac 的最长公共前缀一定也是 abc 和 abcd 的公共前缀。
function longestCommonPrefix(strs) {
let min = 0, max = 0;
for (let i=0; i<strs.length; i++) {
if (strs[min] > strs[i]) {
// 记录最小字符串下标
min = i;
}
if (strs[max] < strs[i]) {
// 记录最大字符串下标
max = i;
}
}
for (let i=0; i<strs[min].length; i++) {
if (strs[min].charAt(i) !== strs[max].charAt(i)) {
return strs[min].substring(0, i);
}
}
return strs[min];
}时间复杂度:O(n+m),n是数组的长度,m是字符串数组中最短字符的长度
空间复杂度:O(1)

评论
登录后参与技术讨论,分享你的经验与见解。
登录 / 注册暂无评论