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

写在前面：大家好！我是【AI 菌】，一枚爱弹吉他的程序员。我热爱AI、热爱分享、热爱开源！ 这博客是我对学习的一点总结与记录。如果您也对 深度学习、机器视觉、算法、Python、C++ 感兴趣，可以关注我的动态，我们一起学习，一起进步~
我的博客地址为：【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
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
 

二、解题思路

(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); }
};

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
 

测试结果：

复杂度分析；

• 时间复杂度：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; }
};

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
 

测试结果：

复杂度分析

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

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

推荐文章

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

文章来源: ai-wx.blog.csdn.net，作者：AI 菌，版权归原作者所有，如需转载，请联系作者。

原文链接：ai-wx.blog.csdn.net/article/details/114663683