题目

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

示例 1：

  1. 输入：strs = ["flower","flow","flight"]
  2. 输出："fl"

示例 2：

  1. 输入：strs = ["dog","racecar","car"]
  2. 输出：""

解释：输入不存在公共前缀。

提示：
1 <= strs.length <= 200
0 <= strs[i].length <= 200
strs[i] 仅由小写英文字母组成

解题思路

image.png

答案

  1. class Solution:
  2.     def longestCommonPrefix(self, strs: List[str]) -> str:
  3.         if not strs:
  4.             return ""
  6.         prefix, count = strs[0], len(strs)
  7.         for i in range(1, count):
  8.             prefix = self.lcp(prefix, strs[i])
  9.             if not prefix:
  10.                 break
  12.         return prefix
  14.     # 两个字符串互相比较
  15.     def lcp(self, str1, str2):
  16.         # 取最短的字符串长度来比较即可
  17.         length, index = min(len(str1), len(str2)), 0
  18.         while index < length and str1[index] == str2[index]:
  19.             index += 1
  20.         return str1[:index]

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