LeetCode题目（Python实现）：最长公共前缀

野性酷女 2023-07-13 12:13 7阅读 0赞

### 文章目录 ###

*  题目
 *   *  想法一
     *   *  算法实现
         *  执行结果
         *  复杂度分析
     *  水平扫描（和想法一相同，但是更简洁）
     *   *  算法实现
         *  执行结果
     *  字典排序
     *   *  算法实现
         *  执行结果
         *  复杂度分析
     *  利用zip
     *   *  算法实现
         *  执行结果
         *  复杂度分析
     *  分治法
     *   *  算法实现
         *  执行结果
         *  复杂度分析
     *  一行代码
     *   *  算法实现
         *  执行结果
     *  小结

# 题目 #

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

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

**示例1** :

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

**示例2** :

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

**说明**:

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

## 想法一 ##

### 算法实现 ###

def longestCommonPrefix(self, strs: List[str]) -> str:
        i = 0
        n = len(strs)
        if n == 0:
            return ""
        elif n == 1:
            return strs[0]
        sMin = len(strs[0])
        for j in range(1, n):
            sMin = min(sMin, len(strs[j]))
        for j in range(sMin):
            temp = strs[0][j]
            flag = 1
            for k in range(1, n):
                if temp != strs[k][j]:
                    flag = 0
                    break
            if not flag:
                break
            i += 1
        return strs[0][:i]

### 执行结果 ###

**执行结果** : 通过  
**执行用时** : 36 ms, 在所有 Python3 提交中击败了72.71%的用户  
**内存消耗** : 13.4 MB, 在所有 Python3 提交中击败了6.57%的用户  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NTU2NTk5_size_16_color_FFFFFF_t_70]

### 复杂度分析 ###

*  时间复杂度：O(kn)，k是字符串中字符最少的长度，n是字符串数量。
 *  空间复杂度：O(1)

## 水平扫描（和想法一相同，但是更简洁） ##

### 算法实现 ###

def longestCommonPrefix(self, strs):
        if not strs:
            return ""
        for i in range(len(strs[0])):
            c = strs[0][i]
            for j in range(len(strs)):
                if i == len(strs[j]) or strs[j][i] != c:
                    return strs[0][: i]
        return strs[0]

### 执行结果 ###

![在这里插入图片描述][20200311235004562.png]

## 字典排序 ##

### 算法实现 ###

def longestCommonPrefix(self, strs):
        if not strs:
            return ""
        strs.sort()
        n = len(strs)
        a = strs[0]
        b = strs[n - 1]
        res = ""
        for i in range(len(a)):
            if i < len(b) and a[i] == b[i]:
                res += a[i]
            else:
                break
        return res

### 执行结果 ###

![在这里插入图片描述][20200314235329443.png]

### 复杂度分析 ###

*  时间复杂度：O(n)，n是字符串数量。
 *  空间复杂度：O(1)

## 利用zip ##

### 算法实现 ###

def longestCommonPrefix(self, strs):
        """
        :type strs: List[str]
        :rtype: str
        """
        res = ""
        for tmp in zip(*strs):
            tmp_set = set(tmp)
            if len(tmp_set) == 1:
                res += tmp[0]
            else:
                break
        return res

### 执行结果 ###

![在这里插入图片描述][20200311224050620.png]

### 复杂度分析 ###

*  时间复杂度：O(n)，n是字符串数量。
 *  空间复杂度：O(1)

## 分治法 ##

### 算法实现 ###

def longestCommonPrefix(self, strs: List[str]):
        if not strs:
            return ""
        return self.longestCommonPrefix5(strs, 0, len(strs) - 1)
    
    def longestCommonPrefix(self, strs: List[str], l: int, r: int):
        if l == r:
            return strs[l]
        else:
            mid = (l + r) // 2
            lcpLeft = self.longestCommonPrefix(strs, l, mid)
            lcpRight = self.longestCommonPrefix(strs, mid + 1, r)
            return self.commonPrefix(lcpLeft, lcpRight)
    
    def commonPrefix(self, left: str, right: str):
        smin = min(len(left), len(right))
        for i in range(smin):
            if left[i] != right[i]:
                return left[: i]
        return left[: smin]

### 执行结果 ###

![在这里插入图片描述][20200311232041791.png]

### 复杂度分析 ###

*  时间复杂度：O(S)，S 是所有字符串中字符数量的总和，S=m\*n。
 *  空间复杂度：O(m⋅log(n))

## 一行代码 ##

### 算法实现 ###

def longestCommonPrefix(self, strs: List[str]) -> str:
        return os.path.commonprefix(strs)

### 执行结果 ###

![在这里插入图片描述][20200311234138578.png]

## 小结 ##

这道题虽然很小，但是能用到的算法可不少，虽然我只想到了一种方法。

然后意外在评论区发现一个惊喜，居然只需要一行，不愧是Python=。=，库函数就是多。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NTU2NTk5_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200311220547313.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NTU2NTk5,size_16,color_FFFFFF,t_70
[20200311235004562.png]: https://img-blog.csdnimg.cn/20200311235004562.png
[20200314235329443.png]: https://img-blog.csdnimg.cn/20200314235329443.png
[20200311224050620.png]: https://img-blog.csdnimg.cn/20200311224050620.png
[20200311232041791.png]: https://img-blog.csdnimg.cn/20200311232041791.png
[20200311234138578.png]: https://img-blog.csdnimg.cn/20200311234138578.png