您好,登录后才能下订单哦!
# LeetCode如何实现最长公共前缀
## 问题描述
在LeetCode的[第14题](https://leetcode.com/problems/longest-common-prefix/)中,要求编写一个函数来查找字符串数组中的最长公共前缀。如果不存在公共前缀,则返回空字符串 `""`。
**示例:**
```python
输入:strs = ["flower","flow","flight"]
输出:"fl"
输入:strs = ["dog","racecar","car"]
输出:""
最直观的方法是依次比较每个字符串的字符,直到找到不匹配的位置。
算法步骤:
1. 取第一个字符串作为初始前缀 prefix
2. 遍历后续字符串,不断缩短 prefix
直到与当前字符串匹配
3. 如果 prefix
为空则提前终止
Python实现:
def longestCommonPrefix(strs):
if not strs:
return ""
prefix = strs[0]
for s in strs[1:]:
while s.find(prefix) != 0:
prefix = prefix[:-1]
if not prefix:
return ""
return prefix
时间复杂度: O(S),其中 S 是所有字符串字符数的总和
逐个字符比较所有字符串的同一位置。
算法步骤: 1. 以第一个字符串为基准 2. 依次比较每个字符串的第i个字符 3. 遇到不匹配时立即返回
Python实现:
def longestCommonPrefix(strs):
if not strs:
return ""
for i in range(len(strs[0])):
char = strs[0][i]
for s in strs[1:]:
if i >= len(s) or s[i] != char:
return strs[0][:i]
return strs[0]
时间复杂度: O(S),最坏情况下仍需比较所有字符
将问题拆分为子问题,合并子问题的解。
算法步骤: 1. 将字符串数组分成左右两部分 2. 分别求出左右两部分的LCP 3. 合并两个LCP的结果
Python实现:
def longestCommonPrefix(strs):
def divide_conquer(l, r):
if l == r:
return strs[l]
mid = (l + r) // 2
lcp_left = divide_conquer(l, mid)
lcp_right = divide_conquer(mid + 1, r)
return common_prefix(lcp_left, lcp_right)
def common_prefix(a, b):
min_len = min(len(a), len(b))
for i in range(min_len):
if a[i] != b[i]:
return a[:i]
return a[:min_len]
if not strs:
return ""
return divide_conquer(0, len(strs) - 1)
时间复杂度: O(S)
对可能的前缀长度进行二分搜索。
算法步骤: 1. 确定最短字符串长度 2. 在 [0, min_len] 范围内二分查找 3. 验证中间长度是否满足公共前缀
Python实现:
def longestCommonPrefix(strs):
if not strs:
return ""
min_len = min(len(s) for s in strs)
low, high = 0, min_len
while low <= high:
mid = (low + high) // 2
if is_common_prefix(strs, mid):
low = mid + 1
else:
high = mid - 1
return strs[0][:high]
def is_common_prefix(strs, length):
prefix = strs[0][:length]
return all(s.startswith(prefix) for s in strs[1:])
时间复杂度: O(S·log n),其中n是最短字符串长度
方法 | 时间复杂度 | 空间复杂度 | 适用场景 |
---|---|---|---|
水平扫描 | O(S) | O(1) | 通用场景 |
垂直扫描 | O(S) | O(1) | 短前缀场景 |
分治法 | O(S) | O(m log n) | 分布式系统 |
二分查找法 | O(S log n) | O(1) | 超长字符串场景 |
最终建议实现:
# 推荐使用垂直扫描法
def longestCommonPrefix(strs):
if not strs:
return ""
for i in range(len(strs[0])):
char = strs[0][i]
for s in strs[1:]:
if i == len(s) or s[i] != char:
return strs[0][:i]
return strs[0]
通过这个问题,我们可以学习到多种算法设计思想在实际问题中的应用,以及如何根据不同的约束条件选择最优解决方案。 “`
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。