[14][简单] 最长公共前缀

题目描述

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

示例 1:

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

示例 2:

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

说明:

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

解题思路

问题简单, 这里记录一个简单高效的算法, 适用于字符串本身较长, 且列表中字符串数量较少的情景.

首先对列表中的字符串进行排序, 正序, 倒序都可. 然后只比较第一个和最后一个字符串即可, 这样的时间复杂度为$O(m\log{m})$. 其中$m$是列表的长度, 时间基本消耗在对列表的排序上了.

代码如下:

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        if len(strs) == 0:
            return ''
        if len(strs) == 1:
            return strs[0]
        strs.sort()
        prefix = ''
        first, last = strs[0], strs[-1]
        if len(first) == 0:
            return prefix
        for i in range(min(len(first), len(last))):
            if first[i] == last[i]:
                prefix += first[i]
            else:
                return prefix
        return prefix

如果用依次比较的方法, 时间复杂度为$O(mn)$, 其中$n$是字符串的平均长度. 在$n \gt \log{m}$的情况下, 用上面这种方法更好.