牛客题霸 [ 最长公共前缀] C++题解/答案

题目描述

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

题解:

原本想暴力做,直接多层循环套,发现并不用
注意本题,给出了多组字符串,求它们的最长公共前缀,这可怎么办?
因为是最长公共前缀,也就是所有字符串都有
我们先将所有字符串排序,越近的字符串最长公共前缀越多,反而越远就越少
所以我们可以直接将排序后的第一个字符串和最后一个字符串对比
因为这两个的公共前缀应该是最少的,如果一个字符串s是他俩的公共前缀,那相比也是其他的前缀了,这样我们就可以只对比两组就实验对比所有组情况
总结下:
就是将最不相同的两个对比找相同,那找到的结果肯定也是满足所有组的

代码:

class Solution {
   
public:
    /** * * @param strs string字符串vector * @return string字符串 */
    string longestCommonPrefix(vector<string>& strs) {
   
        // write code here
        if(strs.empty())return "";
        sort(strs.begin(),strs.end());
        string a=strs[0];
        string b=strs[strs.size()-1];
        int i;
        for(i=0;i<a.size();i++)
        {
   
            if(a[i]!=b[i])break;
        }
        //if(i==a.size())return a;
        return a.substr(0,i);
    }
};