【每日一题】数组系列(3) —— 最长公共前缀

刺骨的言语ヽ痛彻心扉 2022-11-07 05:28 88阅读 0赞

> 写在前面：大家好！我是【AI 菌】，一枚爱弹吉他的程序员。我`热爱AI、热爱分享、热爱开源`！ 这博客是我对学习的一点总结与记录。如果您也对 `深度学习、机器视觉、算法、Python、C++` 感兴趣，可以关注我的动态，我们一起学习，一起进步~  
> 我的博客地址为：[【AI 菌】的博客][AI]  
> 我的Github项目地址是：[【AI 菌】的Github][AI _Github]

--------------------

链接：https://leetcode-cn.com/problems/longest-common-prefix/  
来源：力扣（LeetCode）

--------------------

## 一、题目描述 ##

编写一个函数来查找字符串数组中的最长公共前缀。
    如果不存在公共前缀，返回空字符串 ""。
    
    示例 1：
    输入：strs = ["flower","flow","flight"]
    输出："fl"
    
    示例 2：
    输入：strs = ["dog","racecar","car"]
    输出：""
    解释：输入不存在公共前缀。
    
    提示：
    0 <= strs.length <= 200
    0 <= strs[i].length <= 200
    strs[i] 仅由小写英文字母组成

## 二、解题思路 ##

### (1) 横向遍历法 ###

解题思路：

如下图所示，依次遍历字符串数组中的每一个字符串：  
![在这里插入图片描述][20210311140707539.png_pic_center]  
具体步骤如下：

*  先计算前两个元素S1和S2的最长公共前缀LSP(S1,S2)，记为S1
 *  再计算是S1与S3的最长公共前缀LSP(S1,S3)，记为S1
 *  依次下去，当遍历完所有的字符串以后，即可得到字符串数组中的最长公共前缀
 *  如果在还未遍历完所有字符串，最长公共前缀已经是空串，则最长公共前缀一定是空串，因此不需要继续遍历剩下的字符串，直接返回空串即可。

C++实现如下：

class Solution { 
    public:
        string longestCommonPrefix(vector<string>& strs) { 
            if(!strs.size()) return "";
            string s1 = strs[0]; //初始化
            for(int i=1; i<strs.size(); ++i){ 
                s1 = lcp(s1, strs[i]); //计算两字符串的最大公共前缀
                if(!s1.size()) break; //如果没有公共字符，则最长公共前缀一定是空串
            }
            return s1;
        }
    	//计算两字符串的最大公共前缀
        string lcp(const string& str1, const string& str2){ 
            int len = min(str1.size(), str2.size());
            int index = 0;
            while(index < len && str1[index] == str2[index]){ 
                ++index;
            }
            return str1.substr(0, index);
        }
    };

测试结果：  
![在这里插入图片描述][20210311142815685.png_pic_center]  
复杂度分析；

*  时间复杂度：O(mn)，其中 m 是字符串数组中的字符串的平均长度，n 是字符串的数量。最坏情况下，字符串数组中的每个字符串的每个字符都会被比较一次。
 *  空间复杂度：O(1)。使用的额外空间复杂度为常数。

注：根据数据范围可知，处理一次该函数最多需要200x200=4x10^4次操作。如果计算机一秒能处理10e6次，那么该函数处理一次最多耗时0.04s

### (2) 纵向遍历法 ###

解题思路：

如下图所示，将字符串数组按照如下方式横向摆布：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dqaW5qaWU_size_16_color_FFFFFF_t_70_pic_center]  
具体步骤如下：

*  按照纵向方向遍历，判断所有字符串的第i个元素strs\[\]\[i\]是否相等，如果相等继续遍历
 *  如果不相等，停止遍历，并返回前i个公共的字符：strs\[0\].substr(0, i+1)

C++代码如下:

class Solution { 
    public:
        string longestCommonPrefix(vector<string>& strs) { 
            string out_str;
            if(!strs.size()) return "";
            int len = strs[0].size();//第一个字符串的长度
            for(int i=0; i<len; ++i){ 
                for(int j=1; j<strs.size(); ++j){ 
                    if(strs[j][i]!=strs[0][i])
                        return out_str;
                }
                out_str = strs[0].substr(0, i+1);
            }
            return out_str;
        }
    };

测试结果：  
![在这里插入图片描述][20210311160452488.png]

复杂度分析

*  时间复杂度：O(nm)，其中 m 是字符串数组中的字符串的平均长度，n 是字符串的数量。
 *  空间复杂度：O(1)，使用的额外空间复杂度为常数。

--------------------

***由于水平有限，博客中难免会有一些错误，有纰漏之处恳请各位大佬不吝赐教！***

![在这里插入图片描述][2020090613542669.png_pic_center]  
***推荐文章***

*  [【C++21天养成计划】不聊学习只谈干货（Day1）][C_21_Day1]
 *  [【人生苦短，我学 Python】序言——不学点Python你就out了？][Python_Python_out]
 *  [TF2.0深度学习实战（一）：分类问题之手写数字识别][TF2.0]

[AI]: https://blog.csdn.net/wjinjie
[AI _Github]: https://github.com/Keyird/DeepLearning-TensorFlow2.0
[20210311140707539.png_pic_center]: /images/20221023/7119302eb13e4657868cb815996eb9e0.png
[20210311142815685.png_pic_center]: /images/20221023/3fc14051f6c74ea4878cc96631b49b9f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dqaW5qaWU_size_16_color_FFFFFF_t_70_pic_center]: /images/20221023/1644d86742bf458e83ddddc57e68a1bd.png
[20210311160452488.png]: /images/20221023/93f33a41327f4d7b8005a49722b2afcf.png
[2020090613542669.png_pic_center]: /images/20221023/b74cf019fac44937a3f664bdf2911b14.png
[C_21_Day1]: https://blog.csdn.net/wjinjie/article/details/105316043
[Python_Python_out]: https://ai-wx.blog.csdn.net/article/details/110674503
[TF2.0]: https://ai-wx.blog.csdn.net/article/details/104700834