14：最长公共前缀

题目描述

题目：

  • 编写一个函数来查找字符串数组中的最长公共前缀。
  • 如果不存在公共前缀，返回空字符串 ""。

示例

示例 1：

输入：strs = ["flower","flow","flight"]
输出："fl"

示例 2：

输入：strs = ["dog","racecar","car"]
输出：""
解释：输入不存在公共前缀。

提示

  • 1 <= strs.length <= 200
  • 0 <= strs[i].length <= 200
  • strs[i] 仅由小写英文字母组成

解题思路

有多种方法可以解决此问题，每种方法都有其特点：

1. 水平扫描法

从前往后扫描每个字符串：

  1. 将第一个字符串假设为最长公共前缀。
  2. 遍历其余字符串，比较每个字符串与当前最长公共前缀，一旦发现不匹配的字符，立即减少公共前缀的长度。
  3. 继续此过程直到遍历完所有字符串。

2. 垂直扫描法

按列比较所有字符串的字符：

  1. 查看所有字符串的第一个字符，如果它们相同，继续到下一列；如果不同，算法结束。
  2. 重复此过程，直到字符串的末尾或者找到一个不匹配的字符。

3. 分治法

将问题分解为更小的子问题：

  1. 将字符串列表分成两半，分别找到每一半的最长公共前缀。
  2. 然后，将这两个前缀的公共部分作为结果。

4. 二分查找法

利用二分查找优化查找过程：

  1. 找到所有字符串中长度的最小值。
  2. 使用二分法在此范围内查找最长公共前缀。
  3. 检查每个字符串在这个中间长度上的前缀是否相同。

代码实现

垂直扫描法

def longestCommonPrefix(strs):
    """
    查找字符串数组中的最长公共前缀
    
    Args:
        strs: 字符串数组
        
    Returns:
        str: 最长公共前缀
    """
    if not strs:
        return ""

    # 找到最短字符串的长度
    min_length = min(len(s) for s in strs)

    # 逐列比较字符
    for i in range(min_length):
        char = strs[0][i]
        if any(s[i] != char for s in strs):
            return strs[0][:i]

    return strs[0][:min_length]

zip 方法

使用 Python 的 zip 函数进行字符比较：

from typing import List

def longestCommonPrefix(strs: List[str]) -> str:
    """
    使用 zip 函数查找最长公共前缀
    """
    res = ""
    for chars in zip(*strs):
        if len(set(chars)) == 1:
            res += chars[0]
        else:
            break
    return res

复杂度分析

  • 时间复杂度：O(S)，其中 S 是所有字符串中字符数量的总和
  • 空间复杂度：O(1)，只需要常数级别的额外空间

方法比较

  1. 垂直扫描法

    • 优点：实现简单，直观
    • 缺点：需要遍历所有字符

  2. zip 方法

    • 优点：代码简洁，利用 Python 内置函数
    • 缺点：可能消耗更多内存

注意：

  • 处理空字符串数组
  • 考虑字符串长度不一的情况
  • 注意内存使用效率

函数 reversed：reversed()指南

最近更新时间: