Python求一批字符串的最长公共前缀算法示例
作者:lin-chang 发布时间:2021-03-10 13:40:37
标签: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程序设计有所帮助。
来源:https://blog.csdn.net/u011583025/article/details/84887909
0
投稿
猜你喜欢
- 本文实例为大家分享了python使用PIL剪切图片和拼接图片的具体代码,供大家参考,具体内容如下因工作需要,接触到了PIL这个包,看其他人的
- 先 Create table 吧create table emp(id int not null primary key,name varc
- 实例一--爬取页面import requestsurl="https//itemjd.com/2646846.html"
- 分组条形图拓展一下问题复杂度:使用水平条形图展示每位员工前三个月的销售额。此时,我们需要将每位员工的销售额按月分组,分别绘制条形图进行展示。
- 步骤:Settings-->Editor-->Colors & Fonts-->Font然后在size
- 2021年7月1日,官方正式发布了1.0Datatable版本。1.0版本支持windows和linux,以及Macos。 具体文档可以见:
- 本文实例为大家分享了python实现飞船大战的具体代码,供大家参考,具体内容如下上篇博文我们一起实现了贪吃蛇与坦克大战200行python代
- 前言保留小数位是我们经常会碰到的问题,尤其是刷题过程中。那么在python中保留小数位的方法也非常多,但是笔者的原则就是什么简单用什么,因此
- 在最近一次项目有一个需求,点击按钮——异步提交——异步响应返回——根据响应返回值新开窗口。这有两个要点:异步响应之前不知道要打开窗口的URL
- 做开发中难免时间类型之间的转换, 最近就发现前端js和后端django经常要用到这个转换, 其中jsDate.now()精确到毫秒,而Pyt
- 解决Microsoft VBScript 运行时错误 (0x800A0046) 没有权限的解决方案,0x800a0046错误。前段时间在做站
- 1、同级目录下调用若在程序 testone.py 中导入模块 testtwo.py , 则直接使用【import testtwo 或 fro
- tensorflow官方提供了3种方法来读取数据:预加载数据(preloaded data):在TensorFlow图中定义常量或变量来保存
- 在python中的数据类型和控制流这篇文章中我们提到过列表,它是基本的数据类型之一。通俗来说,它就是用来存储一系列数据的。比如存储一个班级的
- Python 多线程多线程类似于同时执行多个不同程序,多线程运行有如下优点:使用线程可以把占据长时间的程序中的任务放到后台去处理。用户界面可
- 此程序主要是针对某个目录下的全部文件进行筛选,会删除重复的文件。原理很简单,会计算每个文件的哈希,将哈希存入一个字典,文件名对应哈希。imp
- 统计分析常常会出错、存在偏见或过于狭隘。数字崇拜者常因专注于统计分析而把可用性研究引入歧途。强调洞察力和定性研究更为重要。用户研究有两种类型
- 博主作为爬虫初学者,本次使用了requests和beautifulsoup库进行数据的爬取爬取网站:http://datachart.500
- 名片管理系统有两个模块组成:cards_main.py 和 cards_tools.py一个是主程序,另一个是封装增删改查函数的被调用程序代
- 在设计网页时,没有比页面的外观更重要的了。所以,如果发现设计人员十分关注字体及字体大小,我并不感到惊奇。使用CSS来编辑字体有各种各样的方法