学习分治的写法和二分查找提升速度的应用

题目描述

方法一：纵向扫描

遍历第一个字符串，与列表中的其他字符串的相同位置字符逐一比对

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        if len(strs) == 0:
            return ''
        common_prefix = ''

        for i, cur in enumerate(strs[0]):
            for j in range(len(strs)):
                if i >= len(strs[j]) or cur != strs[j][i]:
                    return common_prefix
            common_prefix += cur
        return common_prefix

复杂度分析

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

方法二：横向扫描

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)$。使用的额外空间复杂度为常数。

方法三：分治（递归）

注意到 $\text{LCP}$ 的计算满足结合律，有以下结论：
$$LCP\left(S_1\dots S_n\right)=LCP\left(LCP\left(S_1\dots S_k\right),LCP\left(S_{k+1}\dots S_n\right)\right)$$

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        def lcp(start, end):
            if start == end:
                return strs[start]

            mid = (start + end) // 2
            lcpLeft, lcpRight = lcp(start, mid), lcp(mid + 1, end)
            minLength = min(len(lcpLeft), len(lcpRight))
            for i in range(minLength):
                if lcpLeft[i] != lcpRight[i]:
                    return lcpLeft[:i]

            return lcpLeft[:minLength]

        return "" if not strs else lcp(0, len(strs) - 1)

复杂度分析

• 时间复杂度：$O(mn)$，其中 $m$ 是字符串数组中的字符串的平均长度，$n$ 是字符串的数量。时间复杂度的递推式是 $T(n)=2\cdot T(\frac{n}{2})+O(m)$，通过计算可得 $T(n)=O(mn)$。
• 空间复杂度：$O(m\log n)$，其中 $m$ 是字符串数组中的字符串的平均长度，$n$ 是字符串的数量。空间复杂度主要取决于递归调用的层数，层数最大为 $\log n$，每层需要 $m$ 的空间存储返回结果。

方法四：二分查找（可能是一种较快方法）

显然，最长公共前缀的长度不会超过字符串数组中的最短字符串的长度。用 $\text{minLength}$ 表示字符串数组中的最短字符串的长度，则可以在 $[0,\text{minLength}]$ 的范围内通过二分查找得到最长公共前缀的长度。每次取查找范围的中间值 $\text{mid}$，判断每个字符串的长度为 $\text{mid}$ 的前缀是否相同，如果相同则最长公共前缀的长度一定大于或等于 $\text{mid}$，如果不相同则最长公共前缀的长度一定小于 $\text{mid}$，通过上述方式将查找范围缩小一半，直到得到最长公共前缀的长度。

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        def isCommon(length):
            str0, count = strs[0][:length], len(strs)
            return all(strs[i][:length] == str0 for i in range(1, count))

        if not strs:
            return ''
        minLength = min([len(x) for x in strs])
        left = 0
        right = minLength
        while(left < right):
            mid = (left + right + 1) // 2
            if isCommon(mid):
                left = mid
            else:
                right = mid - 1
        return strs[0][:left]

复杂度分析

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