[Leetcode 14] 最长公共前缀

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。
notion image
复杂度:时间 O(mn);空间 O(1)

解法三:二分查找

思路:
最长公共前缀的长度一定不会超过 最短字符串的长度。 我们可以对这个长度区间 [0, minLen] 进行 二分查找。
检查所有字符串是否共享长度为 mid 的前缀;成立则右移,否则左移。
复杂度:时间 O(n * m * log m)(每次校验 O(n*m),共 log m 次);空间 O(1)
上一篇
[Leetcode 11] 盛最多水的容器
下一篇
[Leetcode 17] 电话号码的字母组合