LeetCode如何解决字符串中最长公共前缀

在LeetCode上，寻找字符串数组中的最长公共前缀是一个常见的面试题。这个问题要求我们找到一组字符串中所有字符串共有的最长前缀。本文将详细介绍如何通过不同的方法来解决这个问题，并分析每种方法的时间复杂度和空间复杂度。

问题描述

给定一个字符串数组 strs，要求找到这些字符串的最长公共前缀。如果不存在公共前缀，返回空字符串 ""。

示例 1:

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

示例 2:

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

方法一：水平扫描法

思路

水平扫描法的基本思路是依次比较每个字符串的字符，直到找到不匹配的字符为止。具体步骤如下：

1. 假设第一个字符串为最长公共前缀 prefix。
2. 遍历数组中的每个字符串，逐个字符与 prefix 进行比较。
3. 如果发现不匹配的字符，则将 prefix 截断到当前匹配的位置。
4. 重复上述步骤，直到遍历完所有字符串或 prefix 为空。

代码实现

def longestCommonPrefix(strs):
    if not strs:
        return ""
    
    prefix = strs[0]
    for s in strs[1:]:
        while s.find(prefix) != 0:
            prefix = prefix[:-1]
            if not prefix:
                return ""
    return prefix

复杂度分析

• 时间复杂度: O(S)，其中 S 是所有字符串中字符的总数。最坏情况下，所有字符串都相同，我们需要比较所有字符。
• 空间复杂度: O(1)，只使用了常数级别的额外空间。

方法二：垂直扫描法

思路

垂直扫描法的基本思路是逐个字符比较所有字符串的相同位置。具体步骤如下：

1. 从第一个字符开始，依次比较每个字符串的当前字符。
2. 如果所有字符串的当前字符都相同，则继续比较下一个字符。
3. 如果发现不匹配的字符，则返回当前已匹配的前缀。

代码实现

def longestCommonPrefix(strs):
    if not strs:
        return ""
    
    for i in range(len(strs[0])):
        char = strs[0][i]
        for s in strs[1:]:
            if i >= len(s) or s[i] != char:
                return strs[0][:i]
    
    return strs[0]

复杂度分析

• 时间复杂度: O(S)，其中 S 是所有字符串中字符的总数。最坏情况下，所有字符串都相同，我们需要比较所有字符。
• 空间复杂度: O(1)，只使用了常数级别的额外空间。

方法三：分治法

思路

分治法的基本思路是将字符串数组分成两部分，分别求出每部分的最长公共前缀，然后再合并结果。具体步骤如下：

1. 将字符串数组分成左右两部分。
2. 递归地求出左半部分的最长公共前缀 left_prefix 和右半部分的最长公共前缀 right_prefix。
3. 合并 left_prefix 和 right_prefix，得到最终的最长公共前缀。

代码实现

def longestCommonPrefix(strs):
    if not strs:
        return ""
    
    def commonPrefix(left, right):
        min_len = min(len(left), len(right))
        for i in range(min_len):
            if left[i] != right[i]:
                return left[:i]
        return left[:min_len]
    
    def divideAndConquer(strs, l, r):
        if l == r:
            return strs[l]
        mid = (l + r) // 2
        left_prefix = divideAndConquer(strs, l, mid)
        right_prefix = divideAndConquer(strs, mid + 1, r)
        return commonPrefix(left_prefix, right_prefix)
    
    return divideAndConquer(strs, 0, len(strs) - 1)

复杂度分析

• 时间复杂度: O(S)，其中 S 是所有字符串中字符的总数。分治法的时间复杂度与水平扫描法和垂直扫描法相同。
• 空间复杂度: O(m * log n)，其中 m 是字符串的平均长度，n 是字符串的数量。递归调用栈的深度为 log n，每次递归调用需要 O(m) 的空间。

方法四：二分查找法

思路

二分查找法的基本思路是通过二分查找来确定最长公共前缀的长度。具体步骤如下：

1. 找到字符串数组中最短字符串的长度 min_len。
2. 在 [0, min_len] 范围内进行二分查找，找到最长的公共前缀长度。
3. 每次二分查找时，检查所有字符串的前 mid 个字符是否相同。

代码实现

def longestCommonPrefix(strs):
    if not strs:
        return ""
    
    min_len = min(len(s) for s in strs)
    low, high = 0, min_len
    
    while low <= high:
        mid = (low + high) // 2
        if isCommonPrefix(strs, mid):
            low = mid + 1
        else:
            high = mid - 1
    
    return strs[0][:high]
    
def isCommonPrefix(strs, length):
    prefix = strs[0][:length]
    for s in strs[1:]:
        if not s.startswith(prefix):
            return False
    return True

复杂度分析

• 时间复杂度: O(S * log m)，其中 S 是所有字符串中字符的总数，m 是最短字符串的长度。二分查找的次数为 log m，每次查找需要 O(S) 的时间。
• 空间复杂度: O(1)，只使用了常数级别的额外空间。

总结

本文介绍了四种解决LeetCode上最长公共前缀问题的方法：水平扫描法、垂直扫描法、分治法和二分查找法。每种方法都有其独特的思路和实现方式，且在不同情况下具有不同的性能表现。在实际应用中，可以根据具体需求选择合适的方法来解决问题。