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

yipeiwu_com6年前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读取excel表格生成erlang数据

为了将excel数据自动转换成所需要的erlang数据,听同事说使用python会很方便简单,就自学了两天python,写了一个比较粗糙的python脚本,不过能用,有什么优化的地方请指...

PyQt5每天必学之拖放事件

PyQt5每天必学之拖放事件

在PyQt5教程的这一部分,我们将讨论拖放操作。 在电脑图形用户界面,拖放事件就是点击一个虚拟对象,并将其拖动到其他位置或到另一个虚拟物体的动作。在一般情况下,它可以被用于调用多种动作,...

Python中subprocess模块用法实例详解

本文实例讲述了Python中subprocess模块用法。分享给大家供大家参考。具体如下: 执行命令: >>> subprocess.call(["ls", "-l...

对python中url参数编码与解码的实例详解

一、简介 在python中url,对于中文等非ascii码字符,需要进行参数的编码与解码。 二、关键代码 1、url编码 对字符串编码用urllib.parse包下的quote(stri...

以Flask为例讲解Python的框架的使用方法

以Flask为例讲解Python的框架的使用方法

了解了WSGI框架,我们发现:其实一个Web App,就是写一个WSGI的处理函数,针对每个HTTP请求进行响应。 但是如何处理HTTP请求不是问题,问题是如何处理100个不同的URL。...