最长公共前缀

虾米哥 阅读:814 2020-10-22 16:37:29 评论:0

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

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

示例 1:

输入: ["flower","flow","flight"]
输出: "fl"
示例 2:

输入: ["dog","racecar","car"]
输出: ""
解释: 输入不存在公共前缀。
说明:

所有输入只包含小写字母 a-z 。

解:

当字符串数组长度为 0 时则公共前缀为空,直接返回
令最长公共前缀 ans 的值为第一个字符串,进行初始化
遍历后面的字符串,依次将其与 ans 进行比较,两两找出公共前缀,最终结果即为最长公共前缀
如果查找过程中出现了 ans 为空的情况,则公共前缀不存在直接返回
时间复杂度:O(s)O(s),s 为所有字符串的长度之和

class Solution { 
public: 
    string longestCommonPrefix(vector<string>& strs) { 
        string str_front; 
 
        for(int i=0;i<strs.size();i++) 
        { 
            if(i==0) 
            { 
                str_front=strs[i]; 
                continue;             
            } 
            int num=min(str_front.size(),strs[i].size()); 
            string front_tmp; 
            for(int index=0;index<num;index++) 
            { 
                //前面不相等,后面就不用比了 
                if(str_front[index]==strs[i][index]) 
                { 
                    front_tmp+=str_front[index]; 
                } 
                else 
                { 
                    break; 
                } 
            } 
            if(front_tmp.size()==0) 
            { 
                return front_tmp; 
            } 
            else 
            { 
                str_front=front_tmp; 
            } 
        } 
        return str_front; 
    } 
};

 

标签:加密算法
声明

1.本站遵循行业规范,任何转载的稿件都会明确标注作者和来源;2.本站的原创文章,请转载时务必注明文章作者和来源,不尊重原创的行为我们将追究责任;3.作者投稿可能会经我们编辑修改或补充。

关注我们

一个IT知识分享的公众号