LeetCode – 14. 最长公共前缀

题目描述

给你一个字符串数组 strs，找到该数组中最长的公共前缀。

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

提示:

  • 所有字符串只包含小写字母。
  • 1 <= strs.length <= 200
  • 0 <= strs[i].length <= 200

示例

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

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

问题分析

这个问题要求我们从多个字符串中找出它们的最长公共前缀。显然，最简单的解决方案是逐字符对比每个字符串的对应位置，直到遇到不匹配的字符为止。

解题思路

有几种常见的解法可以考虑：

  1. 逐字符对比法：我们可以逐个比较所有字符串的每个字符，直到某一位置不匹配为止。只要有一个字符串的当前字符与其它字符串的当前字符不匹配，就返回当前匹配的部分。
  2. 纵向扫描法：对每个字符串的相同位置进行比较，找到第一个不相等的位置。
  3. 水平扫描法：将所有的字符串一一比较，逐步缩小公共前缀。
  4. 分治法：将字符串数组一分为二，分别找出两部分的公共前缀，然后再取两部分公共前缀的公共前缀。
  5. 二分法：通过查找前缀的长度来确定最大公共前缀。

在这道题中，我们使用纵向扫描法来解决问题，它的时间复杂度是 O(N * M)，其中 N 是字符串的个数，M 是字符串的最大长度。

算法步骤

  1. 假设第一个字符串是公共前缀，遍历字符串数组中的每个字符串：
    • 比较当前字符串和当前公共前缀的字符。
    • 如果当前字符串不包含公共前缀，则减少公共前缀的长度。
    • 一旦公共前缀长度变为 0，直接返回空字符串。
  2. 最终得到的公共前缀就是最长公共前缀。

代码实现

class Solution:
    def longestCommonPrefix(self, strs):
        if not strs:
            return ""
        
        # 假设第一个字符串为公共前缀
        prefix = strs[0]
        
        for string in strs[1:]:
            # 遍历每个字符串，逐个字符比较
            while not string.startswith(prefix):
                # 如果当前字符串不以 prefix 开头，缩短 prefix
                prefix = prefix[:-1]
                if not prefix:
                    return ""
        
        return prefix

代码解释

  1. 初始化前缀：我们假设第一个字符串 strs[0] 是最长公共前缀。
  2. 遍历字符串数组：对数组中剩余的每个字符串进行比较：
    • 如果当前字符串以 prefix 开头，继续对下一个字符串进行检查。
    • 如果不以 prefix 开头，则不断缩小 prefix，直到找到一个匹配的前缀或者 prefix 变为空。
  3. 返回结果：最终返回得到的公共前缀。如果在任何时候，prefix 变为空，说明没有公共前缀，直接返回空字符串。

时间复杂度

  • 假设字符串数组中有 n 个字符串，每个字符串的长度为 m。
  • 在最坏的情况下，我们需要对每个字符串的所有字符进行比较，因此时间复杂度为 O(n * m)，其中 n 是字符串的数量，m 是最长字符串的长度。

空间复杂度

  • 空间复杂度是 O(1)，因为我们只使用了常数空间来存储前缀。

示例

  1. 示例 1:输入: strs = ["flower", "flow", "flight"] 输出: "fl" 解释：所有字符串的公共前缀是 "fl"。
  2. 示例 2:输入: strs = ["dog", "racecar", "car"] 输出: "" 解释：没有公共前缀。
  3. 示例 3:输入: strs = ["apple", "apricot", "ap"] 输出: "ap"

总结

这个问题考察了字符串的处理技巧，特别是如何高效地查找多个字符串的公共前缀。通过逐步缩短公共前缀并与其他字符串进行比较，我们可以高效地得到答案。