014. 最长公共前缀 | Leetcode题解

作者：不正经 | 2024-05-07 04:02:38

踩

最长公共前缀

点击上方“蓝色字体”，选择“设为星标”

每天复习一道面试题，轻松拿大厂Offer~

题目描述:

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

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

示例1:


输入:["flower","flow","flight"]
输出: "fl"

示例2:


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

说明:

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

难度：

难度：简单
支持语言：JavaScript、Python、C++、Java

复杂度分析

时间复杂度：O(mn)O(mn)，其中 mm 是字符串数组中的字符串的平均长度，nn 是字符串的数量。最坏情况下，字符串数组中的每个字符串的每个字符都会被比较一次。
空间复杂度：O(1)O(1)。使用的额外空间复杂度为常数。

思路1:

标签：链表
当字符串数组长度为 0 时则公共前缀为空，直接返回
令最长公共前缀 ans 的值为第一个字符串，进行初始化
遍历后面的字符串，依次将其与 ans 进行比较，两两找出公共前缀，最终结果即为最长公共前缀
如果查找过程中出现了 ans 为空的情况，则公共前缀不存在直接返回
时间复杂度：O(s)O(s)O(s)，s 为所有字符串的长度之和

思路2:

标签：链表
当字符串数组长度为 0 时则公共前缀为空，直接返回
令最长公共前缀 ans 的值为第一个字符串，进行初始化
遍历后面的字符串，依次将其与 ans 进行比较，两两找出公共前缀，最终结果即为最长公共前缀
如果查找过程中出现了 ans 为空的情况，则公共前缀不存在直接返回
时间复杂度：O(s)O(s)O(s)，s 为所有字符串的长度之和

代码

JavaScript 实现


/**
 * @来源： Javascript中文网 - 前端进阶资源教程 https://www.javascriptc.com/
 * @介绍：一个致力于帮助开发者用代码改变世界为使命的平台，每天都可以在这里找到技术世界的头条内容
 * @param {string[]} strs
 * @return {string}
 */
var longestCommonPrefix = function(strs) {
  if(strs.length===0)return ''
  let comPre=strs[0]
  for(let i=1;i<strs.length;i++){
    let j=0
    for(;j<strs[i].length;j++){
      if(strs[i][j]!==comPre[j])break
    }
    if(j===0)return ''
    comPre=comPre.substring(0,j)
  }
  return comPre
};


/**
 * @param {string[]} strs
 * @return {string}
 */
var longestCommonPrefix = function(strs) {
    if(strs.length == 0)
        return "";
    let ans = strs[0];
    for(let i =1;i<strs.length;i++) {
        let j=0;
        for(;j<ans.length && j < strs[i].length;j++) {
            if(ans[j] != strs[i][j])
                break;
        }
        ans = ans.substr(0, j);
        if(ans === "")
            return ans;
    }
    return ans;
};


/**
 * @param {string[]} strs
 * @return {string}
//作者：shetia
//链接：https://leetcode-cn.com/problems/longest-common-prefix/solution/zhong-suo-zhou-zhi-zhe-shi-dao-yue-du-ti-by-shetia/
 */
var longestCommonPrefix = function(strs) {
  let str = strs[0]
  if(!str) return ''
  let res = ''
  for(let i = 0; i < str.length; i++){
    let flag = strs.every(item => item[i] == str[i])
    if (flag) {
      res += str[i]
    }else {
      return res
    }
  }
  return res
};

Java 实现


//作者：guanpengchn
// 链接：https://leetcode-cn.com/problems/longest-common-prefix/solution/hua-jie-suan-fa-14-zui-chang-gong-gong-qian-zhui-b/
class Solution {
    public String longestCommonPrefix(String[] strs) {
        if(strs.length == 0)
            return "";
        String ans = strs[0];
        for(int i =1;i<strs.length;i++) {
            int j=0;
            for(;j<ans.length() && j < strs[i].length();j++) {
                if(ans.charAt(j) != strs[i].charAt(j))
                    break;
            }
            ans = ans.substring(0, j);
            if(ans.equals(""))
                return ans;
        }
        return ans;
    }
}

C++ 实现


// 作者：LeetCode-Solution
// 链接：https://leetcode-cn.com/problems/longest-common-prefix/solution/zui-chang-gong-gong-qian-zhui-by-leetcode-solution/
class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        if (!strs.size()) {
            return "";
        }
        string prefix = strs[0];
        int count = strs.size();
        for (int i = 1; i < count; ++i) {
            prefix = longestCommonPrefix(prefix, strs[i]);
            if (!prefix.size()) {
                break;
            }
        }
        return prefix;
    }
 
    string longestCommonPrefix(const string& str1, const string& str2) {
        int length = min(str1.size(), str2.size());
        int index = 0;
        while (index < length && str1[index] == str2[index]) {
            ++index;
        }
        return str1.substr(0, index);
    }
};

python 实现

思路：

解题思路，很容易想到的是我们将第一个字符串A和第二个字符串B求公共前缀，然后在和第三个字符串C求公共前缀，最终得到最长公共前缀。解题重点是求两个字符串求公共前缀。比较常见的想法是如果这两个字符串的第一个字符相同则记录第一个字符，第二个相同则增加第二个，直到出现不同的字符串。但是在这个思路上有一个难点，我们在和C串求前缀的时候，会重新从第一个字符开始记录，增加不必要的计算。第二个思路就是将A串作为前缀，如果与B串前面字符不同，则去掉最后一个字符重新和B串匹配，直到字符完全匹配B串，在python中，s = s[:-1]很容易去掉最后一个字符。实现如下：


#作者：you-yuan-de-cang-qiong
#链接：https://leetcode-cn.com/problems/longest-common-prefix/solution/zi-dian-xu-zui-da-he-zui-xiao-zi-fu-chuan-de-gong-/
 
class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        if not strs: return ""
        str0 = min(strs)
        str1 = max(strs)
        for i in range(len(str0)):
            if str0[i] != str1[i]:
                return str0[:i]
        return str0


 
class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        if len(strs) == 0:
            return ''
        s = strs[0]
        for i in range(1, len(strs)):
            while strs[i].find(s) != 0 :
                s = s[:-1]
        return s

其他

原题leetcode链接：https://leetcode-cn.com/problems/longest-common-prefix/
合作方：JavaScript中文网 – 全球极客挚爱的技术成长平台
说明：leetcode 题解 | 每日一题???? 所有题目并非全部为本人解答，部分为在复习学习中整理提取其他解题作者的优秀笔记，便于大家学习共同进步，如有侵权，请联系删除。

- 完 -

关注公众号「前端布道师」，做前端技术的传播者！