leetcode 14. 最长公共前缀

​
​

作者简介：C/C++ 、Golang 领域耕耘者，创作者
个人主页：作者主页
活动地址：CSDN21天学习挑战赛
题目来源： leetcode官网
如果感觉博主的文章还不错的话，还请关注 、点赞 、收藏🧡三连支持一下博主哦~~~

题目描述

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

如果不存在公共前缀，返回空字符串 “”。

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

示例1：

输入：strs = [“flower”,“flow”,“flight”]
输出：“fl”
示例 2：

示例2：

输入：strs = [“dog”,“racecar”,“car”]
输出：“”
解释：输入不存在公共前缀。

🧡 算法分析

此题方法是依次枚举即可

先取出第一个字符串中的一个字符，然后依次和后面的字符串进行比较

算法步骤

1. 取出第一个字符，这里直接取strs数组中，第一个字符串的每个字符与后面的进行比较

2. 循环后面数组中字符串中的元素进行比较

3. 判断条件，不符合直接返回保存的字符串

   • 遍历的字符串小于原先的字符串
   • 后面的字符串对应位置的字符和第一个字符串中对应位置不同

代码实现

class Solution {
    
public:
    string longestCommonPrefix(vector<string>& strs) {
    
        string re;
        if(strs.empty()) return "";

        for(int i = 0; ; i ++)
        {
    
            if(i >= strs[0].size()) return re;
            char c = strs[0][i];
            for(auto& str : strs)
            {
    
                if(str.size() < i || str[i] != c)
                {
    
                    return re;
                }
                    
            }
            re  += c;
        }
        return re;
    }
};

执行结果：

时间复杂度分析

其中需要数组中每个字符串， 时间复杂度为O(nm)

如果觉得对你有帮助的话:
点赞，你的认可是我创作的动力！
🧡 收藏，你的青睐是我努力的方向！
️ 评论，你的意见是我进步的财富！