C++如何实现最长公共前缀

这篇文章主要为大家展示了“C++如何实现最长公共前缀”，内容简而易懂，条理清晰，希望能够帮助大家解决疑惑，下面让小编带领大家一起研究并学习一下“C++如何实现最长公共前缀”这篇文章吧。

一、题目描述

编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀，返回空字符串 ""。

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

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

二、解题思路

(1) 横向遍历法

解题思路：

如下图所示，依次遍历字符串数组中的每一个字符串：

具体步骤如下：

• 先计算前两个元素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);}};

测试结果：

复杂度分析；

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

• 空间复杂度：O(1)。使用的额外空间复杂度为常数。

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

(2) 纵向遍历法

解题思路：

如下图所示，将字符串数组按照如下方式横向摆布：

具体步骤如下：

• 按照纵向方向遍历，判断所有字符串的第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;}};

测试结果：

复杂度分析

• 时间复杂度：O(nm)，其中 m 是字符串数组中的字符串的平均长度，n 是字符串的数量。

• 空间复杂度：O(1)，使用的额外空间复杂度为常数。

以上是“C++如何实现最长公共前缀”这篇文章的所有内容，感谢各位的阅读！相信大家都有了一定的了解，希望分享的内容对大家有所帮助，如果还想学习更多知识，欢迎关注亿速云行业资讯频道！