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& strs) {         if(!strs.size()) return "";string s1 = strs[0]; //初始化for(int i=1; i
测试结果：

复杂度分析；
时间复杂度：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& strs) {         string out_str;if(!strs.size()) return "";int len = strs[0].size();//第一个字符串的长度for(int i=0; i
测试结果：
复杂度分析
时间复杂度：O(nm)，其中 m 是字符串数组中的字符串的平均长度，n 是字符串的数量。
空间复杂度：O(1)，使用的额外空间复杂度为常数。
以上是"C++如何实现最长公共前缀"这篇文章的所有内容，感谢各位的阅读！相信大家都有了一定的了解，希望分享的内容对大家有所帮助，如果还想学习更多知识，欢迎关注行业资讯频道！