type
status
date
summary
tags
category
icon
password
featured
freq
difficulty
编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀,返回空字符串
""。示例 1:
示例 2:
解法一:横向扫描
思路:从第一个串开始,依次与下一个串求两者 LCP,用结果作为“当前前缀”继续合并;若前缀变空可提前返回。
复杂度:时间
O(mn)(m 平均长度,n 数量);空间 O(1)。解法二:纵向扫描(最优)
思路:以
strs[0] 为“模板”,从左到右枚举列 i,检查所有字符串在 i 位置的字符是否一致;首次不一致前的部分即为 LCP。
复杂度:时间
O(mn);空间 O(1)。解法三:二分查找
思路:
最长公共前缀的长度一定不会超过 最短字符串的长度。
我们可以对这个长度区间 [0, minLen] 进行 二分查找。
检查所有字符串是否共享长度为
mid 的前缀;成立则右移,否则左移。复杂度:时间
O(n * m * log m)(每次校验 O(n*m),共 log m 次);空间 O(1)。- 作者:Fan Luo
- 链接:https://fanluo.me/article/leetcode-14-最长公共前缀
- 声明:本文采用 CC BY-NC-SA 4.0 许可协议,转载请注明出处。
上一篇
[Leetcode 11] 盛最多水的容器
下一篇
[Leetcode 17] 电话号码的字母组合