Python实现字符串集最长公共前缀算法详解

沈知远

发布时间：2026-10-12| 5人浏览过

原创

本文介绍利用Python求解字符串集合最长公共前缀的具体方法。核心思路是先对字符串列表按长度排序，以最短字符串为基准进行逐字符比对。遍历过程中一旦发现字符不一致即返回此前缀，否则返回最短字符串本身。文章附带完整Python代码及运行结果展示，适用于基础算法学习与字符串处理场景。

该问题旨在给定一组字符串后，找出其中共同拥有的最长前缀部分。虽然这与求解最长公共子序列有相似之处，但求解公共前缀的逻辑更为直接。由于前缀必须从字符串起始位置开始匹配，因此只需依次遍历字符即可。当遍历到达字符串末尾，或在结束前遇到不匹配的字符时，即可终止遍历并返回不匹配位置之前的子串。以下是具体的代码实现方案：

#!usr/bin/env python
#encoding:utf-8
 
'''
__Author__:沂水寒城
功能：求解字符串集的最长公共前缀
'''
 
def find_longest_prefix(str_list):
 '''
 求解字符串集的最长公共前缀
 '''
 str_list.sort(lambda x,y:cmp(len(x),len(y)))
 shortest_str=str_list[0]
 print str_list
 max_prefix=len(shortest_str)
 flag=0
 for i in range(max_prefix):
  for one_str in str_list:
   if one_str[i]!=shortest_str[i]:
    return shortest_str[:i]
    break
 return shortest_str
 
 
if __name__ == '__main__':
 str_list1=['abcdef','abcdekljjh','abcdelopqwe','abcdj']
 str_list2=['abcdef','abcdekljjh','abcdelopqwe','abcde']
 print 'str_list1--->', find_longest_prefix(str_list1)
 print 'str_list2--->', find_longest_prefix(str_list2)

程序执行后的输出结果如下所示：

str_list1---> ['abcdj', 'abcdef', 'abcdekljjh', 'abcdelopqwe']
abcd
str_list2---> ['abcde', 'abcdef', 'abcdekljjh', 'abcdelopqwe']
abcde
[Finished in 0.3s]

上述关于使用Python求解字符串集最长公共前缀的方法即为本文分享的全部内容，希望能为读者提供有价值的参考，同时也欢迎大家继续支持本站获取更多技术内容。