最长公共前缀 leetcode 14

moumangtai 2020-01-01 原文

方法一（纵向扫描）

解题思路

先计算出数组中最小的字符串长度，这样就避免了越界的情况，思路更加明确，但同时时间复杂度就相应的上升了。

先计算所有字符串在同一列上的字符是否相同，然后依次向后延伸。

代码及注释

class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        //如果数组中没有字符串,则直接返回空字符串
        if(strs.size()==0) return "";
        //结果字符串
        string ans = "";
        int n = strs[0].size();
        for(int i=1;i<strs.size();i++){
            if(strs[i].size()<n){
                n=strs[i].size();
            }
        }
        //利用前一个和后一个字符串所对应的字符是否相等判断是否具有公共前缀
        //没有则直接退出返回当前ans
        int flag = 0;
        for(int i=0;i<n;i++){
            for(int j=0;j<strs.size()-1;j++){
                if(strs[j][i]!=strs[j+1][i]){
                    flag = 1;
                    break;
                }
            }
            if(flag==1){
                return ans;
            }
            ans+=strs[0][i];
        }
        return ans;
        
    }
};

方法二（水平扫描法）

思路

将第一个字符作为ans，然后不断和后面的字符串进行计算他们的公共前缀然后更新，最后的结果即为最长公共前缀

代码及注释

class Solution {
public:
    //返回两个字符串的公共前缀
    string CommonPrefix(string a,string b){
        int i=0,j=0;
        string t = "";
        while(i<a.size()&&j<b.size()&&a[i]==b[j]){
            t+=a[i];
            i++;
            j++;
        }
        return t;
    }
    string longestCommonPrefix(vector<string>& strs) {
        //数组长度为0返回空字符串
        if(strs.size()==0) return "";
        //数组长度为1返回第一个字符串
        if(strs.size()==1) return strs[0];
        //将第一个字符串作为ans，不断与后面的字符串计算公共前缀然后更新ans，如果ans为空则直接返回ans;
        string ans = strs[0];
        for(int i=1;i<strs.size();i++){
            ans = CommonPrefix(ans,strs[i]);
            if(ans=="") return ans;
        }
        return ans;
    }
};

方法三（分治法）

思路

代码及注释

class Solution {
public:
    //返回两个字符串的公共前缀
    //也是分治法的合
    string merge(string a,string b){
        int i=0,j=0;
        string t = "";
        while(i<a.size()&&j<b.size()&&a[i]==b[j]){
            t+=a[i];
            i++;
            j++;
        }
        return t;
    }
    //分治法的分
    string divide(vector<string>& strs,int left,int right){
        //当分到最后只有一个字符串时直接返回,因为一个字符串的公共前缀就是他的本身
        if(left==right){
            return strs[left];
        }else{
            //将数组一分为二
            int mid = (left+right)/2;
            string leftString = divide(strs,left,mid);
            string rightString = divide(strs,mid+1,right);
            //再通过合并各个分组的公共前缀
            return merge(leftString,rightString);
        }
    }
    string longestCommonPrefix(vector<string>& strs) {
        //数组长度为0返回空字符串
        if(strs.size()==0) return "";
        //数组长度为1返回第一个字符串
        if(strs.size()==1) return strs[0];
        
        //利用分治法计算
        return divide(strs,0,strs.size()-1);
    }
};