题目描述

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

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

样例

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

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

限制

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

算法

(暴力枚举) $O(nm)$

1. 暴力枚举方法很简单：先找到所有字符串的最短长度 m，然后从长度 1 到 m 依次枚举判断是否所有字符串的前缀是否都相等。
2. 注意输入可能为空数组。

时间复杂度

• 最坏情况下，对于 $n$ 个字符串，都需要遍历到最短长度，故总时间复杂度为 $O(nm)$。

空间复杂度

• 需要额外 $O(m)$ 的空间存储答案。

C++ 代码

class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        int n = strs.size();

        if (n == 0)
            return "";

        size_t m = strs[0].length();

        for (int i = 1; i < n; i++)
            m = min(m, strs[i].length());

        for (int s = 1; s <= m; s++) {
            char c = strs[0][s - 1];
            for (int i = 1; i < n; i++)
                if (strs[i][s - 1] != c)
                    return strs[0].substr(0, s - 1);
        }

        return strs[0].substr(0, m);
    }
};