题目描述

[EN | CN]

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

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

示例 1:

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

示例 2:

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

说明:

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

解法 1:直接法

从前往后直接遍历每一位,如果所有字符串的该位(例如第一位、第二位、……)都相同,那么继续,直到遇到不相同的则返回。

这个思路很直接,但其实这里有挺多暗坑容易跪,具体看代码吧。

假设数组长度为 $n$,最短字符串长度为 $m$,那么

  • 时间复杂度为 $O(nm)$,要遍历到最短字符串完;
  • 空间复杂度为 $O(1)$。

实现与结果如下:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        if len(strs) == 0:
            return ''
        if len(strs) == 1:
            return strs[0]

        min_len = min([len(s) for s in strs])
        for i in range(min_len):
            if len(set([s[i] for s in strs])) != 1:
                return strs[0][:i]

        return strs[0][:min_len]
  • 执行用时:40 ms,在所有 Python3 提交中击败了 64.00% 的用户。
  • 内存消耗:13.7 MB,在所有 Python3 提交中击败了 5.31% 的用户。

解法 2:二分查找

第一种方法的改进版,遍历的时候不要一位一位遍历,直接按二分来。

假设数组长度为 $n$,最短字符串长度为 $m$,那么

  • 时间复杂度为 $O(n\log_2 m)$,一共 $\log_2 m$ 次迭代,每次 $n$ 次比较;
  • 空间复杂度为 $O(1)$。

实现与结果略。