14. 最长公共前缀 (opens new window)

题目：

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

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

示例：

示例 1：

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

示例 2：

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

提示：

• 1 <= strs.length <= 200
• 0 <= strs[i].length <= 200
• strs[i] 仅由小写英文字母组成

解题：

方法一：字符串排序

通过排序，将字符串数组中的相似字符串放在一起，使得最长公共前缀出现在排序后的第一个字符串和最后一个字符串之间。然后通过比较这两个字符串找出最长公共前缀。这样的实现在一些情况下可以提高效率，尤其是当字符串数组中的字符串较长时。

这种实现方法的思路可以总结为以下几步：

1. 处理边界情况： 首先检查输入的字符串数组是否为空，如果为空，直接返回空字符串，因为在空数组中不存在公共前缀。

2. 对字符串数组排序： 使用 std::sort 对字符串数组进行排序，这样数组中的字符串就按照字典序排列。

3. 比较排序后的首尾字符串： 取排序后的数组的第一个字符串为 first_str，最后一个字符串为 last_str。

4. 寻找最长公共前缀： 通过比较 first_str 和 last_str 的每个字符，逐个检查它们是否相等，直到遇到不相等的字符或者其中一个字符串结束。在这个过程中，将相等的字符逐个添加到 common_prefix 中。

5. 返回结果： 最终返回得到的 common_prefix，即为排序后的字符串数组中的最长公共前缀。

这种方法的优势在于通过排序的方式，将相似的字符串靠在一起，从而简化了寻找最长公共前缀的过程。不过需要注意，这种方法可能在某些情况下效率较高，但在某些情况下排序的开销可能会比水平扫描法更大。选择适当的方法取决于具体的应用场景和输入数据的特点。

class Solution {
public:
    std::string longestCommonPrefix(std::vector<std::string>& strs) {
        if (strs.empty()) {
            return "";
        }
        std::sort(strs.begin(), strs.end());
        std::string first_str = strs[0];
        std::string last_str = strs[strs.size() - 1];
        std::string common_prefix = "";
        int i = 0;
        while (i < first_str.size() && i < last_str.size() && first_str[i] == last_str[i]) {
            common_prefix += first_str[i];
            i++;
        }
        return common_prefix;
    }
};

可调试的代码

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

class Solution {
public:
    std::string longestCommonPrefix(std::vector<std::string>& strs) {
        if (strs.empty()) {
            return "";
        }
        std::sort(strs.begin(), strs.end());
        std::string first_str = strs[0];
        std::string last_str = strs[strs.size() - 1];
        std::string common_prefix = "";
        int i = 0;
        while (i < first_str.size() && i < last_str.size() && first_str[i] == last_str[i]) {
            common_prefix += first_str[i];
            i++;
        }
        return common_prefix;
    }
};

int main() {
    // 示例输入
    std::vector<std::string> strs = {"flower", "flow", "flight"};
    // 创建 Solution 对象
    Solution solution;
    // 查找最长公共前缀
    std::string result = solution.longestCommonPrefix(strs);
    // 输出结果
    std::cout << "最长公共前缀: " << result << std::endl;
    return 0;
}

复杂度分析

• 时间复杂度：
  • 排序字符串数组的时间复杂度为 O(nlog~n~)，其中 n 是字符串数组的长度。
  • 找到最长公共前缀的过程需要遍历排序后的首尾字符串，最坏情况下需要 O(m) 次比较，其中 m 是最长公共前缀的长度。

综合起来，排序的时间复杂度是主导因素，因此整体的时间复杂度为 O(nlog~n~)。

• 空间复杂度：
  • 除了输入和输出之外，额外使用了一些常量级的空间，比如 first_str、last_str、common_prefix 以及一些循环变量。这些空间的使用与输入规模无关，可以看作是常数级别的。
  • 如果忽略常数级别的空间，整体空间复杂度为 O(1)。

综合起来，这个算法的时间复杂度为 O(nlog~n~)，空间复杂度为 O(1)。

其他解法 LeetCode 也很详细

14. 最长公共前缀 - 力扣（LeetCode） (opens new window)