LeetCode 14.最长公共前缀（字符串）

素颜马尾好姑娘i 2022-11-27 15:59 154阅读 0赞

**上一篇博客：[Leetcode 13.罗马数字转整数（字符串）][Leetcode 13.]**

>  写在前面：大家好！我是`ACfun`,我的昵称来自两个单词`Accepted`和`fun`。我是一个热爱ACM的蒟蒻。最近萌生了刷LeetCode的想法，所以我打算从LeetCode简单的题目开始做起，攻陷LeetCode。如果博客中有不足或者的错误的地方欢迎在评论区或者私信我指正，感谢大家的不吝赐教。我的唯一博客更新地址是：[https://ac-fun.blog.csdn.net/][https_ac-fun.blog.csdn.net]。非常感谢大家的支持。一起加油，冲鸭！  
>  `用知识改变命运，用知识成就未来！加油 (ง •̀o•́)ง (ง •̀o•́)ง`

原题链接：[LeetCode 14.最长公共前缀  
][LeetCode 14._]

### 文章目录 ###

*  题目信息
 *   *  题目描述
     *  示例
     *   *  示例 1
         *  示例 2
     *  说明
 *  题解
 *   *  解题思路
     *  解题代码
     *  提交情况

# 题目信息 #

## 题目描述 ##

编写一个函数来查找字符串数组中的最长公共前缀。如果不存在公共前缀，返回空字符串 `""`。

## 示例 ##

### 示例 1 ###

> 输入: \[“flower”,“flow”,“flight”\]  
> 输出: “fl”

### 示例 2 ###

> 输入: \[“dog”,“racecar”,“car”\]  
> 输出: “”  
> 解释: 输入不存在公共前缀。

## 说明 ##

所有输入只包含小写字母 `a-z` 。

# 题解 #

## 解题思路 ##

最简单的思路就是从前往后循环遍历每一个字符串的每一位，使用两重循环，第一重循环 **i** 用来记遍历的字符串的第几位，第二重循环 **j** 用来记录遍历到第几个字符串。 依次将每一个字符串的每一位与第一个字符串对应位置的字符进行比较，如果当前位置所有的字符都相同那么就将其加入到返回结果 **ans** 中，否则就直接将当前 **ans** 中的值`return`，因为已经遇到不同的字符了，说明当前的 **ans** 就是最长的公共前缀了。

还有一种情况就是遇到更短的字符串的时候，也说明当前的 **ans** 就是最长的公共前缀，此时也直接`return ans；`即可。还要特别注意输入字符串为空的情况，如果 **strs** 是一个空的`vector`，那么我们直接返回空的 **ans** 即可。所以在进行遍历之前我们需要首先特判一下 **strs** 是否为空。  
![图解1][1]  
![图解2][2]

## 解题代码 ##

class Solution { 
    public:
        string longestCommonPrefix(vector<string>& strs) { 
            string ans = "";
            if (strs.empty()) return ans;
            for (int i = 0; i < strs[0].size(); i++) { 
                char ch = strs[0][i];
                for (int j = 0; j < strs.size(); j++) { 
                    if (strs[j].size() <= i || strs[j][i] != ch) { 
                        return ans;
                    }
                }
                ans += ch;
            }
            return ans;
        }
    };

## 提交情况 ##

![提交情况][20200816150101441.png]

--------------------

> 未完待续，持续更新中……  
> ![review][]

[Leetcode 13.]: https://ac-fun.blog.csdn.net/article/details/108029287
[https_ac-fun.blog.csdn.net]: https://ac-fun.blog.csdn.net/
[LeetCode 14._]: https://leetcode-cn.com/problems/longest-common-prefix/
[1]: /images/20221124/c7374824d2b94dcda02a12bc42bf1b54.png
[2]: /images/20221124/7b9c963304d443c8867b36c5c6f58c77.png
[20200816150101441.png]: /images/20221124/aa489c9ba5534076bfcb062b956b1280.png
[review]: /images/20221124/1bf7127bd11b411ba7f6cc79d90e4171.png