精选50题之 14. 最长公共前缀

矫情吗；* 2024-04-17 21:25 54阅读 0赞

### 腾讯精选练习（50 题）之 14. 最长公共前缀 ###

*   *  原题目链接
     *  直接实现

## [原题目链接][Link 1] ##

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

示例 1:

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

示例 2:

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

说明:所有输入只包含小写字母 a-z 。

## 直接实现 ##

从第一个字母开始，在向量中所有字符串的“前缀”必须一致，连续比较。任意一个字符串的一个位置不符合，即认为不存，返回空。

正因为题目中的约束条件很明确且严格，所以解决思路可以很简单（常规）。

PS.  
这就是一个Trade-Off：

1.  题目描述的问题越特殊，越严格，常规思路就可以有不错的结果，代码一般有简单
2.  题目描述的问题越一般，越开放，常规思路一般效果就不太好了，代码复杂，可能会有“特效算法”。

当然，使用数学知识和代码复杂程度是负相关（多用数学，少写代码?）。

所以，除了特殊情况可以直接返回结果外，以第一个字符串作为目标，从第一个元素开始，逐个扫描其余每个字符串对应位置元素，判断是否相等。若相等，继续下一个元素判断；出现不同，返回已匹配的“前缀”。

代买如下

class Solution {
        
    public:
        string longestCommonPrefix(vector<string>& strs) {
        
            if(strs.size() == 0)
                return "";
            else if(strs.size()==1)
                return strs[0];
            string pre = ""; //定义前缀
            for(int i = 0; i < strs[0].size(); i++) //每个字符串的第i个元素
            {
        
                for(int j = 0; j < strs.size(); j++)//第j个字符串
                {
        
                    if(strs[0][i] != strs[j][i])
                        return pre;
                }
                pre += strs[0][i];
            }
            return pre;
        }
    };

运行结果，效果不错  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTcyODQzMQ_size_16_color_FFFFFF_t_70]  
复杂度分析

1.  时间复杂度：O(n)，总字符串数量，线性级；比较过程中是O(n^2)；
2.  空间复杂度：O(1)，只有一个额外空间，常数级。

吐槽下提交平台：  
连续多次提交的执行结果变化很大，可以理解服务器端的负载不同，但是的确影响通过结果判断效果（如果没有真正计算复杂度），会有如下夸张的结果?  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTcyODQzMQ_size_16_color_FFFFFF_t_70 1]

通过搜索，发现还有其他解法，诸如：分治策略、二分查找等；还有优化，诸如先找出最短的字符串，作为比较目标。

但看起来没有明显的、实质性的提高，那么常规的“题目分析”、“解题思路”、“代码实现”就以后再补充了，未完待续（不存在的）…

[Link 1]: https://leetcode-cn.com/problems/longest-common-prefix/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTcyODQzMQ_size_16_color_FFFFFF_t_70]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/17/d4c30d74adfe49ff99e943ad21971255.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTcyODQzMQ_size_16_color_FFFFFF_t_70 1]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/17/d91af629231f43d58753bcb3af9fc1d4.png