专栏首页freesan44LeetCode 14. 最长公共前缀

LeetCode 14. 最长公共前缀

题目

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

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

示例 1:

输入: ["flower","flow","flight"]
输出: "fl"
示例 2:

输入: ["dog","racecar","car"]
输出: ""
解释: 输入不存在公共前缀。

说明:

所有输入只包含小写字母 a-z 。

解题思路

  1. 二分查找法
class Solution:
    def longestCommonPrefix(self, strs: [str]) -> str:
        if len(strs) <=0 : return ""
        import sys
        minLen = sys.maxsize
        for each in strs:
            if len(each)<minLen:
                minLen = len(each)
        low = 1
        height = minLen
        while low <= height:
            middle = (low + height)//2
            if self.isCommonPrefix(strs,middle) :
                low = middle +1
            else:
                height = middle -1

        return strs[0][0:(low+height)//2]
    #比较字符长度
    def isCommonPrefix(self, strs:[str], length:int) ->bool:
        subStr = strs[0][:length]
        for i in range(1,len(strs)):
            if strs[i][:length] != subStr:
                return False
        return True
  1. 分治法
#分治
class Solution:
    def longestCommonPrefix(self, strs: [str]) -> str:
        if len(strs) <= 0: return ""
        length = len(strs)
        return self.longestCommonPrefix2(strs, 0, length-1)


    def longestCommonPrefix2(self, strs: [str], left: int, right: int) ->str:
        if left == right:
            return strs[left]
        else:
            middle = (left + right) //2
            leftStr = self.longestCommonPrefix2(strs, left, middle)
            rightStr = self.longestCommonPrefix2(strs, middle+1,right)
            return self.isCommonPrefix(leftStr, rightStr)

    #比较字符长度
    def isCommonPrefix(self, leftStr: str, rightStr: str) ->str:
        minLen = min(len(leftStr),len(rightStr))
        for i in range(1, minLen+1):
            # print(i)
            # print(leftStr[:i])
            # print(rightStr[:i])
            if leftStr[:i] != rightStr[:i]:
                return leftStr[:i-1]
        return leftStr[:minLen]

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • ReactiveCocoa使用心得

    5.NSMutableArray 因为NSMutableArray不支持KVO,所以用另外一个方式处理:

    freesan44
  • LeetCode 155. 最小栈

    设计一个支持 push,pop,top 操作,并能在常数时间内检索到最小元素的栈。

    freesan44
  • LeetCode 剑指 Offer 09. 用两个栈实现队列

    用两个栈实现一个队列。队列的声明如下,请实现它的两个函数 appendTail 和 deleteHead ,分别完成在队列尾部插入整数和在队列头部删除整数的功能...

    freesan44
  • A*搜索算法(python)

    F - 方块的总移动代价 G - 开始点到当前方块的移动代价 H - 当前方块到结束点的预估移动代价

    李小白是一只喵
  • Python与Cisco的事儿之三

       以下代码可以实现登录网络设备后通过show cdp nei 命令查看邻居设备,然后利用拼接的方式来增加描述,最后再写进相对应的网络设备的接口。

    py3study
  • Leetcode 783. 二叉搜索树结点最小距离

    二叉搜索树属于有序树结构,一个可以利用的特点就是中序遍历可以得到有序数组,得到有序数组后遍历一次即可得到两节点最小差值。

    zhipingChen
  • Python面向对象总结及类与正则表达式

    和其它编程语言相比,Python 在尽可能不增加新的语法和语义的情况下加入了类机制。

    py3study
  • leetcode: 99. Recover Binary Search Tree

    JNingWei
  • 在 PyQt4 中的菜单和工具栏¶

    QtGui.QMainWindow 类提供了一个应用的主窗口。这使得我们可以创建典型的应用框架,包括状态栏,工具栏和菜单。

    bear_fish
  • 在 PyQt4 中的菜单和工具栏¶

    http://www.cppblog.com/mirguest/archive/2012/02/05/164982.html

    bear_fish

扫码关注云+社区

领取腾讯云代金券