题目

题解

1. 遍历法

  • 时间复杂度$O(S)$（最坏情况）。S是所有字符数量。
  • 空间复杂度$O(1)$
class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {//两种方法。1.遍历法
        //这道题纵向遍历，即比较字符串的每一个字符，挨个比较
        if(strs.empty()) return "";
        for(int j=0; j<strs[0].size(); j++){//外层遍历第几个字符
            for(int i=0; i<strs.size(); i++){//内层遍历几个字符串
                if(j >= strs[i].size() || strs[i][j] != strs[0][j]){//若字符数量超过第一个字符串长度，活着遍历到不同的字符
                    return strs[0].substr(0,j);//直接返回第一个字符串前j个字符
                }
            }
        }
        return strs[0];//若全部遍历完成还未停止，则返回第一个字符串
    }
};

2. 排序法

  • 时间复杂度$O(firstLen + endLen)$（最坏情况）。
  • 空间复杂度$O(1)$
class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {//两种方法。2. 排序比较首尾法
    if(strs.empty()) return "";
    sort(strs.begin(),strs.end());
    int i = 0, len = min(strs[0].size(),strs.back().size());
    while(i<len && strs[0][i] == strs.back()[i]) i++;
    //直接比较首位的字符串，当字符数量超过短的字符串或者某个字符不相等时，返回前i个数，因为i为下标，所以取长度时要加1，最后一个++就是这个作用
    return strs[0].substr(0,i); 
    }
};