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;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

执行结果：

💙 时间复杂度分析

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

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