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 实现求解字符串集的最长公共前缀方法就是小编分享给大家的全部内容了，希望能给大家一个参考，也希望大家多多支持我们。

赞 (0)

相关推荐

  • Python使用回溯法子集树模板获取最长公共子序列（LCS）的方法

    Python使用回溯法子集树模板获取最长公共子序列（LCS）的方法

    本文实例讲述了Python使用回溯法子集树模板获取最长公共子序列(LCS)的方法.分享给大家供大家参考,具体如下: 问题 输入 第1行:字符串A 第2行:字符串B (A,B的长度 <= 1000) 输出 输出最长的子序列,如果有多个,随意输出1个. 输入示例 belong cnblogs 输出示例 blog 分析 既然打算套用回溯法子集树模板,那就要祭出元素-状态空间分析大法. 以长度较小的字符串中的字符作为元素,以长度较大的字符串中的字符作为状态空间,对每一个元素,遍历它的状态空间,其它的事情

  • python特性语法之遍历、公共方法、引用

    一.遍历 通过for...in...的语法结构,我们可以遍历字符串.列表.元组.字典等数据结构. 1.字符串遍历 a_str = "hello world" for char in a_str: print(char,end=' ') 2.列表遍历 a_list = [1,2,3,4,5] for num in a_list: print(num,end=' ') 3.元组遍历 a_tuple =(1,2,3,4,5) for num in a_tuple: print(num,end

  • python 公共方法汇总解析

    1.计算长度 value = "wangdianchao" # 计算字符个数(长度) number = len(value) print(number) 2.索引取值 value = "wangdianchao" # 获取value"0"位置的字符 number = value[0] print(number) value = "wangdianchao" # 获取value右侧第一个的字符 number = value[-1

  • python中找出numpy array数组的最值及其索引方法

    在list列表中,max(list)可以得到list的最大值,list.index(max(list))可以得到最大值对应的索引 但在numpy中的array没有index方法,取而代之的是where,其又是list没有的 首先我们可以得到array在全局和每行每列的最大值(最小值同理) >>> a = np.arange(9).reshape((3,3)) >>> a array([[0, 1, 2], [9, 4, 5], [6, 7, 8]]) >>&

  • 对python的unittest架构公共参数token提取方法详解

    额...每个请求都有token值的传入,但是token非常易变,一旦变化,所有的接口用例都得改一遍token,工作量太大了... 那么有没有一种方法能把token提取出来,作为一个全局变量,作为一个参数,从而牵一发而动全身呢?? 经过探索,具体方案如下 先定义一个全局变量token类型为string 然后把请求链接定义一个变量类型为string 然后定义第三个变量=前两个变量相加 然后requests直接传第三个变量就行了 具体代码如下: class Test(unittest.TestCase

  • python实现求两个字符串的最长公共子串方法

    如下所示: # coding:utf-8 ''' 求两个字符串的最长公共子串 思想:建立一个二维数组,保存连续位相同与否的状态 ''' def getNumofCommonSubstr(str1, str2): lstr1 = len(str1) lstr2 = len(str2) record = [[0 for i in range(lstr2+1)] for j in range(lstr1+1)] # 多一位 maxNum = 0 # 最长匹配长度 p = 0 # 匹配的起始位 for

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

    问题比较简单,给定一个字符串集合求解其中最长的公共前缀即可,这样的问题有点类似于最长公共子序列的问题,但是比求解最长最长公共子序列简单很多,因为是公共前缀,这样的话只需要挨个遍历即可,只要遍历长度结束或者结束前发现有不相同的即可终止,返回不同位置之前的子序列即可,下面是具体的实现: #!usr/bin/env python #encoding:utf-8 ''' __Author__:沂水寒城 功能:求解字符串集的最长公共前缀 ''' def find_longest_prefix(str_li

  • Python实现查找字符串数组最长公共前缀示例

    本文实例讲述了Python实现查找字符串数组最长公共前缀.分享给大家供大家参考,具体如下: 编写一个函数来查找字符串数组中的最长公共前缀. class Solution: def longestCommonPrefix(self, strs): """ :type strs: List[str] :rtype: str """ olds = '' rs='' if not strs: return '' if len(strs)==1: retu

  • python 将列表中的字符串连接成一个长路径的方法

    今天实习公司分配了一个数据处理的任务.在将列表中的字符串连接成一个长路径时,我遇到了如下问题: import os path_list = ['first_directory', 'second_directory', 'file.txt'] print os.path.join(path_list) 发现 os.path.join 之后,依然是字符串列表.这我就纳闷了: ['first_directory', 'second_directory', 'file.txt'] 细思后想明白了,os

  • Python求一批字符串的最长公共前缀算法示例

    Python求一批字符串的最长公共前缀算法示例

    本文实例讲述了Python求一批字符串的最长公共前缀算法.分享给大家供大家参考,具体如下: 思路一:这个题一拿到手,第一反应就是以第一个字符串strs[0]为标准,如果其他字符串的第一个字符和str[0]的第一个字符串相同,则再比较第二个字符串,以此类推直到出现不同为止. def longestCommonPrefix(self, strs): """ :type strs: List[str] :rtype: str """ if not st

  • python对批量WAV音频进行等长分割的方法实现

    对批量WAV音频进行等长分割 对WAV格式的音频以相同长度进行分割. import os import wave import numpy as np import pylab as plt import librosa path = r"D:\cutaudio\test" files = os.listdir(path) files = [path + "\\" + f for f in files if f.endswith('.wav')] CutTime =

  • Python中实现字符串类型与字典类型相互转换的方法

    本文以实例形式简述了Python中字符串类型与字典类型相互转换的方法,是比较实用的功能.具体方法如下: 一.字典(dict)转为字符串(string) 我们可以比较容易的将字典(dict)类型转为字符串(string)类型. 通过遍历dict中的所有元素就可以实现字典到字符串的转换: for key, value in sample_dic.items(): print "\"%s\":\"%s\"" % (key, value) 二.字符串(s

  • python 动态规划问题解析(背包问题和最长公共子串)

    python 动态规划问题解析(背包问题和最长公共子串)

    目录 背包问题 最长公共子串 背包问题 现在要往一个可以装4个单位重量的背包里怎么装价值最高:A重量1个单位,价值15:B重量3个单位,价值20:C重量4个重量,价值30 使用动态规划填充空格 class SolutionBag: def valuableBag(self,optionalList,sizeBig): #创建网格 grid = [[0 for i in range(sizeBig+1)] for j in range(len(optionalList)+1)] #从行列序号1开始

  • Java最长公共子序列示例源码

    最长公共子序列(Longest Common Subsequence)定义:两个或多个已知数列的子序列集合中最长的就是最长公共子序列.其实说到最长公共子序列,还有一个要提到的是最长公共子串(Longest Common Substring),它指的是两个字符串中的最长公共子串,要求子串一定连续.关于最长公共子串的内容我们后续也会讲到,今天先来看下最长公共子序列的相关内容. 之前看过一个LCS算法的实现过程,觉得太过繁琐.自己写了一个比较简单的,此处仅仅介绍实现过程. 程序代码测试通过,需要的童鞋

  • Python求两个字符串最长公共子序列代码实例

    一.问题描述 给定两个字符串,求解这两个字符串的最长公共子序列(Longest Common Sequence).比如字符串1:BDCABA:字符串2:ABCBDAB.则这两个字符串的最长公共子序列长度为4,最长公共子序列是:BCBA 二.算法求解 这是一个动态规划的题目.对于可用动态规划求解的问题,一般有两个特征:①最优子结构:②重叠子问题 ①最优子结构 设X=(x1,x2,...,xn)和Y=(y1,y2,...,ym)是两个序列,将X和Y的最长公共子序列记为LCS(X,Y) 找出LCS(X

随机推荐