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

2. 分治法

   
   

#分治
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]