最长公共前缀代码异常：输入["cir","car"]为何得到"cr"而非"c"

strs = ["cir","car"]
#strs = ["flower","flow","flight"]
def get_min_str(lst):
    return min(lst, key=len)
str1 = get_min_str(strs)

lens = len(strs)
x = ""
mlen = len(str1)

if(lens == 1):
    print(strs[0])

for i in range(0, mlen):
    for j in range(0, lens-1):

       
        if( strs[j][i] == strs[j+1][i] ):
            if(j == lens-2):
                x = x +  strs[j][i]
            print(strs[j][i])
        else:
            break
        print(strs[j][i] == strs[j+1][i])
            
       

print(x)

我编写了一段寻找最长公共前缀的Python代码，采用双层循环实现。当测试输入为strs = ["cir","car"]时，预期公共前缀x为"c"，但实际输出为"cr"。已使用break语句，按逻辑应在"c"后停止，请问异常原因是什么？

问题原因 #

你用的break只能跳出内层的j循环，外层的i循环会继续执行下一轮。比如：

• 当i=1时，内层j=0比较"i"和"a"不相等，执行break跳出内层循环，但外层i会直接走到i=2
• 此时i=2对应两个字符串的第三个字符"r"和"r"，内层判断相等，于是把"r"加到了x里，最终得到错误的"cr"

核心问题就是：内层break没有终止外层的i循环，导致后续不应该被检查的字符被错误匹配。

修正方案 #

可以加一个匹配标志位，在发现不匹配时终止外层循环，代码示例：

strs = ["cir","car"]
#strs = ["flower","flow","flight"]
def get_min_str(lst):
    return min(lst, key=len)
str1 = get_min_str(strs)

lens = len(strs)
x = ""
mlen = len(str1)

if lens == 1:
    print(strs[0])

for i in range(mlen):
    is_match = True
    # 检查所有相邻字符串的当前位置字符
    for j in range(lens - 1):
        if strs[j][i] != strs[j+1][i]:
            is_match = False
            break
    if is_match:
        x += strs[0][i]
    else:
        # 只要有一个位置不匹配，直接终止外层循环
        break

print(x)

逻辑说明 #

1. 每轮外层循环开始时，默认当前位置字符是匹配的
2. 内层循环遍历所有相邻字符串，只要发现不匹配就标记并跳出内层
3. 如果当前位置所有字符都匹配，就把字符加入结果；否则直接终止外层循环，不再检查后续位置

这样就能正确输出预期的"c"。

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