最长公共前缀

难度: 简单

标签: 字典树 字符串

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

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

示例 1：

输入：strs = ["flower","flow","flight"]
输出："fl"

示例 2：

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

提示：

Submission

运行时间: 48 ms

内存: 15 MB

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        def isCommonPrefix(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(s) for s in strs)
        low, high = 0, minLength
        while low < high:
            mid = (high - low + 1) // 2 + low
            if isCommonPrefix(mid):
                low = mid
            else:
                high = mid - 1
    
        return strs[0][:low]
0 0

Explain

此题解采用了二分搜索的方法来寻找最长公共前缀。首先，通过计算所有字符串的最小长度来确定搜索范围，然后使用二分搜索来逐渐缩小可能的公共前缀的长度范围。在每次搜索过程中，都会检查当前中间长度是否为所有字符串的公共前缀，如果是，则尝试增加长度，否则减少长度。这种方法依赖于二分搜索逐步缩小搜索空间，并且在每次迭代中都通过比较切片来检查公共前缀。

时间复杂度: O(m * n * log(m))

空间复杂度: O(m)

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        def isCommonPrefix(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(s) for s in strs)
        low, high = 0, minLength
        # 使用二分搜索确定最长公共前缀的长度
        while low < high:
            mid = (high - low + 1) // 2 + low
            if isCommonPrefix(mid):
                # 如果当前中间长度是公共前缀，则尝试更长的长度
                low = mid
            else:
                # 否则，减少长度范围
                high = mid - 1
    
        # 返回最长公共前缀
        return strs[0][:low]

Explore

在实现二分查找的时候，为什么选择使用`minLength`作为上限进行查找？是否有可能最长公共前缀的长度超过某个字符串的长度？

使用`minLength`作为上限是因为公共前缀的最大可能长度不能超过数组中最短字符串的长度。如果某个前缀长度超过了这个最短的字符串长度，那么这个长度不可能是所有字符串的公共前缀。因此，以最短字符串长度作为搜索的上界是合理且高效的，避免了不必要的比较。

函数`isCommonPrefix`中的比较是基于什么逻辑来确定所有字符串在该长度上具有共同前缀的？

函数`isCommonPrefix`通过比较每个字符串在指定长度的前缀是否相同来工作。具体逻辑是首先取第一个字符串的指定长度为基准前缀，然后遍历其他所有字符串，检查它们在同样长度的前缀是否与基准前缀完全一致。如果所有字符串的前缀都相同，则认为该长度可以作为公共前缀；如果有任何一个不匹配，则该长度不是有效的公共前缀。

在二分查找中，调整`mid`值时，为什么将`high`设置为`mid - 1`而不是`mid`？

在二分查找中，如果已经确定`mid`长度的前缀不是所有字符串的公共前缀，那么没有必要再考虑长度等于或大于`mid`的情况，因此将`high`设置为`mid - 1`，以此缩小查找范围。这是二分查找策略的一部分，旨在有效地减少搜索空间，提高查找效率。

你是如何考虑和处理输入数组为空的情况？

如果输入数组为空，那么按照问题描述和逻辑，不存在任何字符串来确定公共前缀。因此，在函数开始时进行检查，如果数组为空，则直接返回空字符串""作为结果。这种情况的处理是必要的，以防止在空数组上执行后续操作而导致错误。

能否详细解释算法中的时间复杂度`O(m * n * log(minLength))`是如何计算得出的？

这个时间复杂度的计算基于三个主要因素：字符串的平均长度`m`、字符串数组的长度`n`、以及执行二分查找的次数`log(minLength)`。每次二分查找需要调用`isCommonPrefix`函数，该函数遍历所有`n`个字符串，比较它们的长度为`m`的前缀，因此每次调用的时间复杂度为`O(m * n)`。因为二分查找在最坏情况下会执行`log(minLength)`次，所以总的时间复杂度为`O(m * n * log(minLength))`。

在二分查找中，更新`low`和`high`指针的策略会如何影响算法的执行效率？

更新`low`和`high`指针的策略直接影响二分查找的效率和执行次数。正确的更新策略可以快速排除不可能的前缀长度，从而减少不必要的比较。例如，当确定当前`mid`可以作为公共前缀时，适当增加`low`可以帮助我们尝试更长的可能前缀；相反，将`high`减少到`mid - 1`可以帮助快速排除过长的不可能前缀。这种精确控制查找范围的能力是二分查找高效性的关键所在。

返回题目列表