Leetcode|Leetcode 14 最长公共前缀
编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀，返回空字符串 "" 。
【Leetcode|Leetcode 14 最长公共前缀】示例 1：
输入：strs = ["flower","flow","flight"]示例 2：
输出："fl"
输入：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 ，所以不用对空值进行处理
时间复杂度：上面这种方法思路很容易想到，但是需要进行大量的遍历操作，时间复杂度较高。第二种方法是仅比较最大、最小字符串的最长公共前缀。这里说的最大、最小指的是 ACSII 编码的先后顺序，例如O(s)，s是所有字符串中字符数量的总和
空间复杂度：O(1)
ab 小于 abc ，abc 小于 abcd ，abcd 小于 ac ，那么最小 ab 与最大 ac 的最长公共前缀一定也是 abc 和 abcd 的公共前缀。function longestCommonPrefix(strs) {
let min = 0, max = 0;
for (let i=0;
i strs[i]) {
// 记录最小字符串下标
min = i;
}
if (strs[max] < strs[i]) {
// 记录最大字符串下标
max = i;
}
}
for (let i=0;
i时间复杂度：O(n+m)，n是数组的长度，m是字符串数组中最短字符的长度
空间复杂度：O(1)
推荐阅读
- SpringBoot调用公共模块的自定义注解失效的解决
- 【Leetcode/Python】001-Two|【Leetcode/Python】001-Two Sum
- leetcode|leetcode 92. 反转链表 II
- 二叉树路径节点关键值和等于目标值（LeetCode--112&LeetCode--113）
- LeetCode算法题-11.|LeetCode算法题-11. 盛最多水的容器（Swift）
- LeetCode（03）Longest|LeetCode（03）Longest Substring Without Repeating Characters
- Leetcode|Leetcode No.198打家劫舍
- [leetcode数组系列]1两数之和
- 我们都是普通人
- 数据结构和算法|LeetCode 的正确使用方式