如何优化最长公共前缀求解代码以提升运行效率？

我在做一道求一组单词最长公共前缀的代码题，自己写的方案逻辑上能跑，但效率太低没法正常执行，求各位给点优化建议。

测试用例：

• 输入：["flower","flow","flight"]，期望输出："fl"
• 输入：["dog","racecar","car"]，期望输出：""

我的代码如下：

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        if len(strs) == 0:
            return("")
        if len(strs) == 1:
            return(strs[0])
        
        prefix = strs[0]
        wordLength = len(strs)
        
        for i in range(wordLength):
            
            while prefix != strs[i+1]:
                prefix = prefix[:-1]
                
            if len(prefix) == 0:
                return("")
        return(prefix)

原代码存在的问题 #

1. 索引越界bug：循环for i in range(wordLength)会遍历到i = wordLength - 1，此时strs[i+1]会访问超出列表长度的索引，直接报错，这是比效率更严重的问题。
2. 低效的全量比较：每次用while prefix != strs[i+1]做全字符串比较，然后逐个缩短前缀，这种方式会重复比较大量相同字符，比如前缀是"flower"和"flow"比较时，会先比较整个字符串，再比较"flowe"，直到"flow"，做了5次全量比较，效率很低。

优化方案 #

方案1：逐个字符比较，提前截断

遍历每个字符位置，检查所有单词在该位置的字符是否一致，一旦发现不一致，直接返回当前前缀。这种方式只需要遍历到第一个不匹配的位置，避免无效的全量比较。

优化后代码：

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        if not strs:
            return ""
        
        # 以第一个单词为基准，遍历每个字符位置
        for i, char in enumerate(strs[0]):
            # 检查其他所有单词在该位置的字符
            for s in strs[1:]:
                # 如果当前单词长度不足，或者字符不匹配，返回前缀
                if i >= len(s) or s[i] != char:
                    return strs[0][:i]
        # 如果所有字符都匹配，返回第一个单词
        return strs[0]

方案2：横向比较优化（针对原逻辑改进）

保留横向比较的思路，但修复索引问题，并且改为逐个字符匹配前缀，而非全字符串比较：

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        if not strs:
            return ""
        prefix = strs[0]
        for s in strs[1:]:
            # 找到当前前缀和s的最长公共前缀长度
            min_len = min(len(prefix), len(s))
            match_len = 0
            while match_len < min_len and prefix[match_len] == s[match_len]:
                match_len += 1
            prefix = prefix[:match_len]
            if not prefix:
                return ""
        return prefix

优化说明 #

• 两种方案都避免了原代码的索引越界问题，同时将全量字符串比较改为逐个字符比较，减少了不必要的重复比较，时间复杂度从O(nmk)（n是单词数，m是前缀平均长度，k是每次比较的字符数）优化到O(n*m)（m是最短单词长度）。
• 方案1更直观，一旦发现不匹配立即返回，在多数测试用例下能提前终止循环；方案2适合理解横向比较的思路，逐步缩短前缀。

内容的提问来源于stack exchange，提问作者kei