Easy

题目描述

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

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

示例 1：

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

示例 2：

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

提示：

  • 1 <= strs.length <= 200
  • 0 <= strs[i].length <= 200
  • strs[i] 仅由小写英文字母组成（如果非空）

解题思路

这道题有多种解法思路：

方法一：水平扫描法（推荐） 将第一个字符串作为初始公共前缀，然后依次与数组中的每个字符串比较，不断缩短公共前缀。对于每个字符串，从头开始逐字符比较，一旦发现不匹配就停止。这种方法简单直观，易于理解和实现。

方法二：垂直扫描法 逐列比较所有字符串的相同位置字符。先比较所有字符串的第0个字符，如果都相同再比较第1个字符，以此类推。一旦发现某个位置的字符不全相同，就返回到该位置为止的前缀。

方法三：分治法 将字符串数组分成两半，分别求出左半部分和右半部分的最长公共前缀，然后合并两个结果。虽然代码更复杂，但思路清晰。

方法四：二分查找法 在可能的前缀长度范围内进行二分查找，对于每个长度，检查是否所有字符串都包含该长度的相同前缀。

本题解采用水平扫描法，因为它实现简单且效率较高。

代码实现

class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        if (strs.empty()) return "";
        
        string prefix = strs[0];
        for (int i = 1; i < strs.size(); i++) {
            while (strs[i].find(prefix) != 0) {
                prefix = prefix.substr(0, prefix.length() - 1);
                if (prefix.empty()) return "";
            }
        }
        return prefix;
    }
};

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

public class Solution {
    public string LongestCommonPrefix(string[] strs) {
        if (strs.Length == 0) return "";
        
        string prefix = strs[0];
        for (int i = 1; i < strs.Length; i++) {
            while (!strs[i].StartsWith(prefix)) {
                prefix = prefix.Substring(0, prefix.Length - 1);
                if (prefix == "") return "";
            }
        }
        return prefix;
    }
}

/**
 * @param {string[]} strs
 * @return {string}
 */
var longestCommonPrefix = function(strs) {
    if (strs.length === 0) return "";
    
    let prefix = strs[0];
    
    for (let i = 1; i < strs.length; i++) {
        while (strs[i].indexOf(prefix) !== 0) {
            prefix = prefix.substring(0, prefix.length - 1);
            if (prefix === "") return "";
        }
    }
    
    return prefix;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(S)，其中 S 是所有字符串的字符数之和。最坏情况下需要比较所有字符。
空间复杂度O(1)，只使用了常数额外空间（不考虑输入和输出）。

相关题目