Python实现字符串最长公共前缀的两种算法对比

算法核心逻辑

求解最长公共前缀（Longest Common Prefix）的核心在于确定一组字符串共有的起始字符序列。实现该功能通常遵循以下逻辑路径：

1. 基准选取：以列表中的第一个字符串 strs[0] 作为比对基准。
2. 字符遍历：逐个提取基准字符串中的字符，构建潜在的前缀。
3. 一致性校验：检查其他所有字符串是否以当前构建的前缀开头。
4. 终止条件：一旦发现某个字符串不匹配，则截断前缀并返回；若遍历完所有字符均匹配，则返回完整基准字符串。

方法一：基准字符串逐字符比对

该方法直接利用第一个字符串进行迭代，逻辑直观且代码紧凑。它通过累加字符构建前缀，并立即验证其他字符串是否包含该前缀。

def longestCommonPrefix(self, strs):
    """
    :type strs: List[str]
    :rtype: str
    """
    if not strs:
      return ""
    first_str = strs[0]
    other_strs = strs[1:]
    prefix = ""
    for i in first_str:
      prefix += i
      for s in other_strs:
        if not s.startswith(prefix):
          return prefix[:-1]
    return prefix

执行流程解析：

• 首先处理空列表情况，直接返回空字符串。
• 提取第一个字符串 first_str 和剩余字符串列表 other_strs。
• 遍历 first_str 的每个字符 i，将其追加到 prefix。
• 内层循环遍历 other_strs，使用 startswith() 方法校验当前前缀。
• 若发现不匹配，返回截去最后一个字符的前缀（即上一个有效前缀）。
• 若循环结束未返回，说明第一个字符串本身就是最长公共前缀。

方法二：迭代两两求前缀

该方法采用分治思想，先计算前两个字符串的公共前缀，再将该结果与后续字符串依次比较。这种方式将问题分解为多次“两个字符串求前缀”的子任务。

class Solution(object):
  def longestCommonPrefix(self, strs):
    """
    :type strs: List[str]
    :rtype: str
    """
    if not strs:
       return ""
    if len(strs) == 1:
      return strs[0]
    prefix = strs[0]
    for i in range(len(strs)-1):
      if not prefix:
        return ""
      prefix = self.getCommonPrefix(prefix,strs[i+1])
    return prefix
  #先定义一个函数求出两个字符串的最长公共前缀
  def getCommonPrefix(self,str1,str2):
    if not str1 or not str2:
      return ""
    prefix = ""
    for s in str1:
      prefix += s
      if not str2.startswith(prefix):
        return prefix[:-1]
    return prefix

执行流程解析：

• 处理边界情况：空列表返回空字符串，单元素列表直接返回该元素。
• 初始化 prefix 为第一个字符串。
• 遍历列表，每次调用 getCommonPrefix 将当前前缀与下一个字符串合并。
• getCommonPrefix 内部逻辑与方法一类似，但专注于两个字符串的比对。
• 若中间前缀变为空，提前返回空字符串以优化性能。

算法性能对比

在实际测试中，方法一（基准字符串逐字符比对）的执行速度通常快于方法二（迭代两两求前缀）。主要原因如下：

• 函数调用开销：方法二在每次迭代中都需要调用 getCommonPrefix 函数，增加了栈帧创建和销毁的开销。
• 字符串拼接次数：方法一直接在主函数中操作，减少了中间变量的创建和函数传递。
• 短路机制：方法一在发现不匹配时立即返回，而方法二可能需要多次函数调用才能确定最终结果。

尽管方法二在代码结构上更具模块化，适合理解“两两求前缀”的逻辑，但在追求执行效率的场景下，方法一更为推荐。

总结

本文详细展示了Python中求解最长公共前缀的两种经典算法。方法一通过直接遍历基准字符串实现高效比对，适合对性能有要求的场景；方法二通过迭代两两求前缀，逻辑清晰但存在函数调用开销。开发者可根据具体需求选择合适实现。以上就是Python求一批字符串的最长公共前缀算法示例的详细内容，更多关于Python算法优化的资料请关注本站其它相关文章！