arrays - 对于字符串数组中最长的公共(public)前缀字符串，此解决方案的时间复杂度是多少？

Question

这是问题陈述-

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

我不确定下面我的解决方案的时间复杂度。我猜它是 O(nmnlogn)。 nlogn 用于排序，n*m 用于遍历数组，并对字符串进行 m 比较。

string longestCommonPrefix(vector<string>& strs) {
    if(strs.size() == 0) return "";

    sort(strs.begin(), strs.end());

    string prefix = strs[0];
    int length = prefix.length();
    for (int i = 0; i < strs.size(); ++i) {
        if (prefix == strs[i].substr(0, length)) continue;
        if (prefix != strs[i].substr(0, length)) {
            prefix = prefix.substr(0, --length);
            length = prefix.length();
            i = 0;
        }
        if (prefix == "") break;
    }

    return prefix;
}

Answer 1

假设排序后的所有内容都是 O(nm)，那么它将是 O(nlogn + nm)(因为您只进行了一次排序)，这可能可以根据 m 之间的关系进一步简化并登录。