Python求一批字符串的最长公共前缀算法示例
本文实例讲述了Python求一批字符串的最长公共前缀算法。分享给大家供大家参考,具体如下:
思路一:这个题一拿到手,第一反应就是以第一个字符串strs[0]为标准,如果其他字符串的第一个字符和str[0]的第一个字符串相同,则再比较第二个字符串,以此类推直到出现不同为止。
def longestCommonPrefix(self, strs): """ :type strs: List[str] :rtype: str """ if not strs: return "" first_str = strs[0] other_strs = strs[1:] prefix = "" for i in first_str: prefix += i for s in other_strs: if not s.startswith(prefix): return prefix[:-1] return prefix
思路二:第二种方法,就是先比较前两个字符串,求出他们的最长公共前缀,再用这个前缀去跟第三个字符串比较求出新的公共前缀,以此类推
class Solution(object): def longestCommonPrefix(self, strs): """ :type strs: List[str] :rtype: str """ if not strs: return "" if len(strs) == 1: return strs[0] prefix = strs[0] for i in range(len(strs)-1): if not prefix: return "" prefix = self.getCommonPrefix(prefix,strs[i+1]) return prefix #先定义一个函数求出两个字符串的最长公共前缀 def getCommonPrefix(self,str1,str2): if not str1 or not str2: return "" prefix = "" for s in str1: prefix += s if not str2.startswith(prefix): return prefix[:-1] return prefix
不过测试了一下,第一种方法还要快一点。
更多关于Python相关内容感兴趣的读者可查看本站专题:《Python数据结构与算法教程》、《Python列表(list)操作技巧总结》、《Python编码操作技巧总结》、《Python函数使用技巧总结》、《Python字符串操作技巧汇总》及《Python入门与进阶经典教程》
希望本文所述对大家Python程序设计有所帮助。
相关推荐
-
Python查找最长不包含重复字符的子字符串算法示例
本文实例讲述了Python查找最长不包含重复字符的子字符串算法.分享给大家供大家参考,具体如下: 题目描述 请从字符串中找出一个最长的不包含重复字符的子字符串,计算该最长子字符串的长度.例如在"arabcacfr"中,最长的不包含重复字符的子字符串是"acfr",长度为4 采用字典的方法,最后输出所有最长字符的列表 算法示例: # -*- coding:utf-8 -*- #! python3 class Solution: def __init__(self):
-
python之消除前缀重命名的方法
● 脚本用途 遍历文件夹下的文件,消除文件名前的特征字符串. ● 脚本实现 import os,sys import re from string import Template div = r"." ############################################################################### # @Function: description #######################################
-
Python实现的破解字符串找茬游戏算法示例
本文实例讲述了Python实现的破解字符串找茬游戏算法.分享给大家供大家参考,具体如下: 最近在一个QQ群里发现有那种机器人, 发出来字符串找茬游戏: 有点类似于: 没没没没没没没没没没没没没没没没没没 没没没没没没没没没没没没没没没没没没 没没没没没役没没没没没没没没没没没没 没没没没没没没没役没没没没没没没没没 没没没没没没没没没没没没没没没没没没 没没没没没没没没没没没没没没没没没没 玩法就是用户发消息到群里: #找茬 然后群里有个自动聊天的机器人, 他接到这句话之后, 会将上面一大堆文字
-
Python实现常见的回文字符串算法
回文 利用python 自带的翻转 函数 reversed() def is_plalindrome(string): return string == ''.join(list(reversed(string)))` 自己实现 def is_plalindrome(string): string = list(string) length = len(string) left = 0 right = length - 1 while left < right: if string[left]
-
Python实现字符串匹配算法代码示例
字符串匹配存在的问题 Python中在一个长字符串中查找子串是否存在可以用两种方法:一是str的find()函数,find()函数只返回子串匹配到的起始位置,若没有,则返回-1:二是re模块的findall函数,可以返回所有匹配到的子串. 但是如果用findall函数时需要注意字符串中存在的特殊字符 蛮力法字符串匹配: 将模式对准文本的前m(模式长度)个字符,然后从左到右匹配每一对对应的字符,直到全部匹配或遇到一个不匹配的字符.后一种情况下,模式向右移一位. 代码如下: def string_m
-
Python字符串匹配算法KMP实例
本文实例讲述了Python字符串匹配算法KMP.分享给大家供大家参考.具体如下: #!/usr/bin/env python #encoding:utf8 def next(pattern): p_len = len(pattern) pos = [-1]*p_len j = -1 for i in range(1, p_len): while j > -1 and pattern[j+1] != pattern[i]: j = pos[j] if pattern[j+1] == pattern
-
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 re test='kasduabshdvkjASVKDV.txt' m=re.findall(r'(.+?)\.',test) print(m) 我们所使用的是python正则表达式库,re库来进行快速正则匹配.对此不熟悉的朋友可以去看看相关的知识.在这里我简单的说下 r'(.+?)\.'这里面的
-
python 实现求解字符串集的最长公共前缀方法
问题比较简单,给定一个字符串集合求解其中最长的公共前缀即可,这样的问题有点类似于最长公共子序列的问题,但是比求解最长最长公共子序列简单很多,因为是公共前缀,这样的话只需要挨个遍历即可,只要遍历长度结束或者结束前发现有不相同的即可终止,返回不同位置之前的子序列即可,下面是具体的实现: #!usr/bin/env python #encoding:utf-8 ''' __Author__:沂水寒城 功能:求解字符串集的最长公共前缀 ''' def find_longest_prefix(str_li
-
Python求一批字符串的最长公共前缀算法示例
本文实例讲述了Python求一批字符串的最长公共前缀算法.分享给大家供大家参考,具体如下: 思路一:这个题一拿到手,第一反应就是以第一个字符串strs[0]为标准,如果其他字符串的第一个字符和str[0]的第一个字符串相同,则再比较第二个字符串,以此类推直到出现不同为止. def longestCommonPrefix(self, strs): """ :type strs: List[str] :rtype: str """ if not st
-
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
-
C语言求两个字符串的最长公共子串
本文实例讲述了C语言求两个字符串的最长公共子串的方法.分享给大家供大家参考.具体实现方法如下: #include "stdio.h" #include "string.h" #include "stdlib.h" void getCommon(char str1[],char str2[],char * str3); int stringLength(char * str); void main(){ char str1[50]; char st
-
Python最长公共子串算法实例
本文实例讲述了Python最长公共子串算法.分享给大家供大家参考.具体如下: #!/usr/bin/env python # find an LCS (Longest Common Subsequence). # *public domain* def find_lcs_len(s1, s2): m = [ [ 0 for x in s2 ] for y in s1 ] for p1 in range(len(s1)): for p2 in range(len(s2)): if s1[p1] =
-
Ruby实现的最长公共子序列算法
最长公共子序列,LCS,动态规划实现. #encoding: utf-8 #author: xu jin, 4100213 #date: Nov 01, 2012 #Longest-Commom-Subsequence #to find a longest commom subsequence of two given character arrays by using LCS algorithm #example output: #The random character arrays are
-
Python回文字符串及回文数字判定功能示例
本文实例讲述了Python回文字符串及回文数字判定功能.分享给大家供大家参考,具体如下: 所谓回文字符串,就是一个字符串,从左到右读和从右到左读是完全一样的.回文数字也是如此. python2代码如下: def huiwen(s): s1=str(s) if s1==''.join(reversed(s1)): return True else: return False 运行结果: >>> huiwen('abccba') True >>> huiwen('abc')
-
Python实现计算字符串中出现次数最多的字符示例
本文实例讲述了Python实现计算字符串中出现次数最多的字符.分享给大家供大家参考,具体如下: 1. 看了网上挺多写的方法都没达到我所需要的效果,我干脆自己写了个方法共享给大家 ee = 'aa111(((bbhhhhhh%jjjjjj%(ccc((vvvv22' cc='11222333' def max_letter_count(n): list4 = [] list1 = [] list2 = [] for i in n: list3 = [] count_max = n.count(i)
-
Python基于pycrypto实现的AES加密和解密算法示例
本文实例讲述了Python基于pycrypto实现的AES加密和解密算法.分享给大家供大家参考,具体如下: 一 代码 # -*- coding: UTF-8 -*- import string import random from Crypto.Cipher import AES def keyGenerater(length): '''''生成指定长度的秘钥''' if length not in (16, 24, 32): return None x = string.ascii_lette
随机推荐
- asp.net mvc下拉框Html.DropDownList 和DropDownListFor的常用方法
- iOS模仿电子书首页实现书架布局样式
- jquery单行文字向上滚动效果的实现代码
- JQery jstree 大数据量问题解决方法
- asp.net GridView控件鼠标移动某行改变背景颜色(方法一)
- php的array数组和使用实例简明教程(容易理解)
- 使用Python脚本操作MongoDB的教程
- Android中PopupWindow响应返回键并关闭的2种方法
- 在服务端(Page.Write)调用自定义的JS方法详解
- java加密枝术深入理解
- php debug 安装技巧
- java string的一些细节剖析
- Python实现简单的多任务mysql转xml的方法
- 去除某些论坛帖子中自动添加的白色字体即乱码的方法
- Java中ArrayList去除重复元素(包括字符串和自定义对象)
- Java注解Annotation解析
- Android仿知乎客户端关注和取消关注的按钮点击特效实现思路详解
- 一款支持混合多线路接入的LINUX软路由
- 正则表达式模式匹配字符串基础知识
- Python3简单实例计算同花的概率代码