计算最长公共前缀

LeetCode 最长公共前缀

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

如果不存在公共前缀，返回空字符串 “”

在这里对LeetCode上的解法做一个整理

横向扫描

暴力扫描法，每个字符串横向扫描。
先循环比较第一个字符串和第二个字符串每个字符是否相等，找出相同的公共前缀，再将找到的公共前缀与下一个字符串比较，直到字符串全部比较结束或公共前缀为空时，结束循环。

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        if not strs:
            return ''
        
        prefix,count = strs[0],len(strs)
        for i in range(1,count):
            prefix = self.lcp(prefix,strs[i])
            if not prefix:
                break

        return prefix
    
    def lcp(self,str1,str2):
        length,index = min(len(str1),len(str2)), 0
        while index < length and str1[index] == str2[index]:
            index+=1
        return str1[:index]

时间复杂度：O(mn)，其中 m 是字符串数组中的字符串的平均长度，n 是字符串的数量。最坏情况下，字符串数组中的每个字符串的每个字符都会被比较一次。
空间复杂度：O(1)

纵向扫描

纵向扫描，先对比每个字符串的第一个字符，再比较第二个字符，以此类推，字符串扫描完或出现不一样字符时结束循环。

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        if not strs:
            return ""
        
        length,count = len(strs[0]), len(strs)
        for i in range(length): #取第一个字符串中的字符
            c = strs[0][i]
            for j in range(1,count): #依次与每个字符串中对应位置字符比较
                if i == len(strs[j]) or strs[j][i] != c:
                    return strs[0][:i]
                
        return strs[0]

时间复杂度：O(mn)，其中 m 是字符串数组中的字符串的平均长度，n 是字符串的数量。最坏情况下，字符串数组中的每个字符串的每个字符都会被比较一次。
空间复杂度：O(1)

二分查找

用 minLength 表示字符串数组中的最短字符串的长度，在 [0,minLength] 的范围内通过二分查找得到最长公共前缀的长度。每次取查找范围的中间值 mid，判断每个字符串的长度为mid 的前缀是否相同，如果相同则最长公共前缀的长度一定大于或等于 mid，查找后半段字符串。如果不相同则最长公共前缀的长度一定小于 mid，查找前半段字符串。

# 代码来自官方题解
class Solution:   
    def longestCommonPrefix(self, strs: List[str]) -> str:
        def isCommonPrefix(length:int):
            str0, count = strs[0][:length], len(strs)
            return all(strs[i][:length] == str0 for i in range(1,count))
			# all：判断迭代参数中所有元素为True
        if not strs:
            return ""
        
        minLength = min(len(s) for s in strs)
        low, high = 0, minLength
        while high > low: 
            mid = (high - low + 1)//2 + low
            if isCommonPrefix(mid):
                low = mid
            else:
                high = mid - 1
        
        return strs[0][:low]

时间复杂度：O(mnlogm)，其中 m 是字符串数组中的字符串的最小长度，n 是字符串的数量。二分查找的迭代执行次数是O(logm)，每次迭代最多需要比较 mn 个字符，因此总时间复杂度是 O(mnlogm)。
空间复杂度：O(1)

使用python提供的函数

1. zip() 函数用于将可迭代的对象作为参数，将对象中对应的元素打包成一个个元组，然后返回由这些元组组成的列表。
   set() 函数创建一个无序不重复元素集。

class Solution:
    def longestCommonPrefix(self, strs):
        """
        :type strs: List[str]
        :rtype: str
        """
        res = ""
        for tmp in zip(*strs):
            tmp_set = set(tmp)
            if len(tmp_set) == 1:
                res += tmp[0]
            else:
                break
        return res

作者：powcai
链接：https://leetcode-cn.com/problems/longest-common-prefix/solution/duo-chong-si-lu-qiu-jie-by-powcai-2/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

2. 按字典排序数组，比较第一个，和最后一个单词，有多少前缀相同。

class Solution:
    def longestCommonPrefix(self, s: List[str]) -> str:
        if not s:
            return ""
        s.sort()
        n = len(s)
        a = s[0]
        b = s[n-1]
        res = ""
        for i in range(len(a)):
            if i < len(b) and a[i] == b[i]:
                res += a[i]
            else:
                break
        return res

作者：powcai
链接：https://leetcode-cn.com/problems/longest-common-prefix/solution/duo-chong-si-lu-qiu-jie-by-powcai-2/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

本文地址：https://blog.csdn.net/cfslbrn/article/details/107449171