python 实现求解字符串集的最长公共前缀方法

yipeiwu_com5年前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 实现求解字符串集的最长公共前缀方法就是小编分享给大家的全部内容了,希望能给大家一个参考,也希望大家多多支持【听图阁-专注于Python设计】。

相关文章

采用Psyco实现python执行速度提高到与编译语言一样的水平

本文实例讲述了采用Psyco实现python执行速度提高到与编译语言一样的水平的方法,分享给大家供大家参考。具体实现方法如下: 一、安装Psyco很简单,它有两种安装方式,一种是源码方式...

修改 CentOS 6.x 上默认Python的方法

最近在工作中遇到一个问题,就是有一个功能希望在各种服务器上实现,而服务器上的系统版本可能都不一样,有的是 CentOS 6.x,有的是 CentOS 7.x 。 需要说明的一点是,Cen...

python strip()函数 介绍

描述 Python strip() 方法用于移除字符串头尾指定的字符(默认为空格)。 语法 strip()方法语法: str.strip([chars]); 参数 chars -- 移除...

python生成1行四列全2矩阵的方法

如下所示: print np.ones((1,4))*2 以上这篇python生成1行四列全2矩阵的方法就是小编分享给大家的全部内容了,希望能给大家一个参考,也希望大家多多支持【听...

一个基于flask的web应用诞生 组织结构调整(7)

一个基于flask的web应用诞生 组织结构调整(7)

现在所有的Py代码均写在default.py文件中,很明显这种方法下,一旦程序变的负责,那么无论对于开发和维护来说,都会带来很多问题。 Flask框架并不强制要求项目使用特定的组织结构,...