14.最长公共前缀

题目描述

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

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

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

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

注意：

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

答案代码

这道题的思路是判断相邻的两个字符串之间的某个子串是否相同，如果不同就退出循环；相同则继续遍历，当i遍历完后则进入下一个字符。

这个过程中要注意一些特殊情况：没有字符串，只有一个字符串，如果num很大最后需要终止比较。

string longestCommonPrefix(vector<string>& strs) {
        int i=0,num=0;
        string s;
        if(strs.size()==0)return s;
        if(strs.size()==1)return strs[0];
        for(i=0;i<strs.size()-1;i++){
            if(strs[i]=="")return s;
            if(strs[i][num]!=strs[i+1][num])break;
            if(i==strs.size()-2){
                s=s+strs[i][num];
                num+=1;
                i=-1;
            }
            if(num==strs[0].size())break;
        }
        return s;
    }

这个解法的问题是速度比较慢，属于纵向扫描方式。leetcode官方还提供了几个其他方法：

横向遍历

具体代码可以参考：题解

分治法

代码使用了递归方式，具体可以查看题解

二分查找

不断判断左半部分是否相同，但是对于这道题并没有加快速度。

特别解法

评论中有一个特别有意思的解法：

先排序，后比较头尾即可

将字符串组排序后，如果头和尾一致，则整个数组都相同。

string longestCommonPrefix(vector<string>& strs) {
        if(strs.empty()) return string();//判断是否是空字符串组
        sort(strs.begin(), strs.end());//排序
        string st = strs.front(), en = strs.back();
        int i, num = min(st.size(), en.size());//保证不会越界
        for(i = 0; i < num && st[i] == en[i]; i ++);//判断第一个和最后一个有多少个字符相同
        return string(st, 0, i);
    }