【力扣经典面试题】14. 最长公共前缀

目录

一、题目描述

二、解题思路

 三、解题步骤

四、代码实现（C++版详细注释）

五、总结

---

欢迎点赞关注哦！创作不易，你的支持是我的不竭动力，更多精彩等你哦。

一、题目描述

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

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

示例 1：

输入：strs = ["flower","flow","flight"]
输出："fl"

示例 2：

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

提示：

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

二、解题思路

通过示例分析可以发现， 通过遍历每个单词的相同索引下标并且对相应的字母进行对比，只要发现有一个字母不同便结束循环，返回结果。如果所有字母均相同则返回strs[0]。同时如果字符串数组为空则返回空字符。

 三、解题步骤

1. 第一种特殊情况 如果字符串数组为空则返回空字符；

2. 即每次实现单词从左到右逐一遍历，比较相同索引下标的字母是否相同；

3. 直到索引相同下标的字母不同的时候，结束循环，返回结果；

4. 如果所有字母均与第一个单词字母相同，则返回第一个单词strs[0];

四、代码实现（C++版详细注释）

class Solution {
public:string longestCommonPrefix(vector<string>& strs) {// 第一种特殊情况 如果字符串数组为空则返回空字符if (!strs.size()) {return "";}// 正常情况的字符数组情况。首先声明字符第一单词的长度，字符数组长度int length = strs[0].size();int count = strs.size();// 第一for循环// 实现控制单词字母的索引下标，即每次实现单词从左到右逐一遍历for (int i = 0; i < length; ++i) {// 记录每一次需要比较的字母char c = strs[0][i];// 第二个for循环实现除第一个单词以外的所有单词字母对比，其中通过count实现每个单词遍历for (int j = 1; j < count; ++j) {// 通过if判断语句实现// 比较相同索引下标的字母是否相同，如果相同则继续第二个for循环，如果不相同则结束循环，返回遍历结果if (i == strs[j].size() || strs[j][i] != c) {// 因为索引相同下标的字母遇到不同，结束循环，返回结果return strs[0].substr(0, i);}}}// 第三种情况，如果所有字母均与第一个单词字母相同，则返回第一个单词strs[0];return strs[0];}
};

五、总结

时间复杂度分析,即两个for循环。

空间复杂度分析。