LeetCode如何实现最长公共前缀

发布时间:2021-12-15 10:39:27 作者:小新
来源:亿速云 阅读:178
# LeetCode如何实现最长公共前缀

## 问题描述

在LeetCode的[第14题](https://leetcode.com/problems/longest-common-prefix/)中,要求编写一个函数来查找字符串数组中的最长公共前缀。如果不存在公共前缀,则返回空字符串 `""`。

**示例:**
```python
输入:strs = ["flower","flow","flight"]
输出:"fl"

输入:strs = ["dog","racecar","car"]
输出:""

解决思路

1. 水平扫描法(横向比较)

最直观的方法是依次比较每个字符串的字符,直到找到不匹配的位置。

算法步骤: 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 是所有字符串字符数的总和

2. 垂直扫描法(纵向比较)

逐个字符比较所有字符串的同一位置。

算法步骤: 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),最坏情况下仍需比较所有字符

3. 分治法

将问题拆分为子问题,合并子问题的解。

算法步骤: 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)

4. 二分查找法

对可能的前缀长度进行二分搜索。

算法步骤: 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) 超长字符串场景

总结

  1. 对于大多数情况,垂直扫描法实现简单且效率较高
  2. 分治法适合并行计算场景
  3. 二分查找法在字符串非常长时可能有优势
  4. 实际编码时需注意处理空输入等边界条件

最终建议实现:

# 推荐使用垂直扫描法
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]

通过这个问题,我们可以学习到多种算法设计思想在实际问题中的应用,以及如何根据不同的约束条件选择最优解决方案。 “`

推荐阅读:
  1. leetcode--最长公共前缀
  2. LeetCode如何实现跳跃游戏

免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。

leetcode

上一篇:Qt颜色拾取器怎么实现

下一篇:Qt通用数据库翻页查询如何实现

相关阅读

您好,登录后才能下订单哦!

密码登录
登录注册
其他方式登录
点击 登录注册 即表示同意《亿速云用户服务条款》