前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >Python|蓝桥杯之最长公共前缀

Python|蓝桥杯之最长公共前缀

作者头像
算法与编程之美
发布2021-02-24 15:21:45
4690
发布2021-02-24 15:21:45
举报

编写一个函数来查找字符串数组中的最长公共前缀。

如果不存在公共前缀,返回空字符串 ""。

示例 1:

输入:["flower","flow","flight"]

输出: "fl"

示例 2:

输入:["dog","racecar","car"]

输出: ""

解释: 输入不存在公共前缀。

解决方案

很容易想到的是我们将第一个字符串A和第二个字符串B求公共前缀,然后在和第三个字符串C求公共前缀,最终得到最长公共前缀。解题重点是求两个字符串求公共前缀。比较常见的想法是如果这两个字符串的第一个字符相同则记录第一个字符,第二个相同则增加第二个,直到出现不同的字符串。但是在这个思路上有一个难点,我们在和C串求前缀的时候,会重新从第一个字符开始记录,增加不必要的计算。第二个思路就是将A串作为前缀,如果与B串前面字符不同,则去掉最后一个字符重新和B串匹配,直到字符完全匹配B串,在python中,s=s[:-1]很容易去掉最后一个字符。

代码如下:

在代码中要用到find函数,Pythonfind()方法检测字符串中是否包含子字符串str如果指定开始和结束范围,则检查是否包含在指定范围内。

结语

这个问题用到了字符串的检测,通过列表中元素一一比对,查找相同的前缀,如果与B串前面字符不同,则去掉最后一个字符重新和B串匹配,直到字符完全匹配B串。

主编:王楠岚

稿件来源:深度学习与文旅应用实验室(DLETA)

本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2021-02-07,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 算法与编程之美 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档