问题 15：最长公共前缀

Source: Dev.to

问题描述

目标是编写一个函数，找出一组字符串中最长的公共前缀。

• 前缀 是出现在字符串开头的子串。
• 函数应返回所有单词共同开头的最长字符串。
• 如果不存在公共前缀，则返回空字符串 ""。

示例

longest_common_prefix(['flower', 'flow', 'flight'])   # → 'fl'
longest_common_prefix(['dog', 'racecar', 'car'])      # → ''
longest_common_prefix(['interspecies', 'interstellar'])  # → 'inters'

解决方案

def longest_common_prefix(strings):
    """
    Finds the longest common prefix among a list of strings.
    """
    # Check for empty input
    if not strings:
        return ""

    # Start with the first string as the initial prefix
    prefix = strings[0]

    # Compare with each subsequent string
    for s in strings[1:]:
        # Shorten the prefix until it matches the start of the current string
        while not s.startswith(prefix):
            prefix = prefix[:-1]
            # If the prefix becomes empty, there is no common prefix
            if prefix == "":
                return ""

    return prefix

# Test cases
print(longest_common_prefix(['flower', 'flow', 'flight']))      # 'fl'
print(longest_common_prefix(['dog', 'racecar', 'car']))         # ''
print(longest_common_prefix(['interspecies', 'interstellar']))  # 'inters'

代码拆解

函数定义

def longest_common_prefix(strings):

定义一个接受字符串列表的函数。

空输入检查

if not strings:
    return ""

当输入列表为空时返回空字符串。

初始前缀

prefix = strings[0]

假设整个第一个字符串可能是公共前缀。

遍历其余字符串

for s in strings[1:]:

循环处理第一个字符串之后的每个字符串。

缩短前缀

while not s.startswith(prefix):
    prefix = prefix[:-1]
    if prefix == "":
        return ""

不断从 prefix 末尾删除字符，直到当前字符串以它开头。如果 prefix 变为空，则不存在公共前缀。

返回结果

return prefix

所有字符串处理完后，prefix 即为最长公共前缀。

示例演练

示例 1：['flower', 'flow', 'flight']

1. 初始化： prefix = 'flower'
2. 与 'flow' 比较：
   • 'flow' 不以 'flower' 开头 → prefix = 'flowe'
   • 仍不匹配 → prefix = 'flow'（此时匹配）
3. 与 'flight' 比较：
   • 'flight' 不以 'flow' 开头 → prefix = 'flo'
   • 仍不匹配 → prefix = 'fl'（此时匹配）
4. 结果： 'fl'

示例 2：['dog', 'racecar', 'car']

1. 初始化： prefix = 'dog'
2. 与 'racecar' 比较：
   • 不匹配 → prefix = 'do' → 不匹配 → prefix = 'd' → 不匹配 → prefix = ''
3. 结果： ''（无公共前缀）

关键优化

• 水平匹配： 以第一个字符串作为最大可能前缀，仅在出现不匹配时收缩，而不是在所有字符串上逐字符检查。
• 提前退出： 一旦前缀变为空，算法立即停止，避免不必要的比较。

这种方法简洁、易读，且在常见使用场景下效率良好。祝编码愉快！