前往此题

解题思路

一、横向扫描法

根据公式lcp(s1...sn) = lcp(lcp(lcp(s1,s2),s3)...sn) 可以得知：

1. 对比前两个字符串并找到公共前缀
2. 将这个公共前缀与第三个字符串进行对比，再找到新的公共前缀。以此类推

代码

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


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

二、 二分查找

这里我们换一种思路，通过二分查找来找到最长公共前缀的长度。我们知道最长公共前缀的长度是不可能大于最短字符的，记作minLength，所以我们只需要在[0,minLength ]中查找能缩小查找范围。

算法过程

1. 创建minLength, 表示strs中最短字符串的长度
2. 二分查找：在[0, minLength]范围内进行二分查找中间值mid，然后将mid为截取长度与其他字符串进行匹配，直到找到最长公共字符

代码

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        def isCommonPrefix(length):
            str0 = strs[0][:length]
            return all(strs[i][:length] == str0 for i in range(1, len(strs)))
        
        if not strs: return ""
        minLength = min(len(s) for s in strs)
        low, high = 0, minLength
        while low < high:
            mid = low + ((high - low + 1) >> 1)
            if isCommonPrefix(mid):
                low = mid
            else: high = mid - 1
        return strs[0][:low]