题目

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

示例1

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

示例2

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

实现

思路1

同时对多个字符串中的字符进行遍历，例如[“flower”,”flow”,”flight”]，一开始先比较三个字符串的第一个字符”f”，然后比较第二个”l”，直到出现不匹配或者某个字符串遍历结束。

  1. class Solution:
  2.     def longestCommonPrefix(self, strs: List[str]) -> str:
  3.         if not strs:
  4.             return ""
  6.         length, num = len(strs[0]), len(strs)
  7.         for i in range(length):
  8.             c = strs[0][i] # 以第一个字符串作为基准
  9.             for j in range(num):
  10.                 # 如果其它字符串已经遍历结束，或者字符不匹配，就截取字符串
  11.                 if i == len(strs[j]) or c != strs[j][i]:
  12.                     return strs[0][:i]
  13.         # 第一个字符串遍历结束
  14.         return strs[0]

时间复杂度：14. 最长公共前缀 - 图1，其中 mm 是字符串数组中的字符串的平均长度，nn 是字符串的数量。最坏情况下，字符串数组中的每个字符串的每个字符都会被比较一次。
空间复杂度：14. 最长公共前缀 - 图2

思路2

首先拿第一个和第二个字符串求最大前缀，求得的最大前缀再跟第三个字符串求最大前缀……
例如[“flower”,”flow”,”flight”]，首先”flower”与”flow”的最大公共前缀为”flow”，下一步就用”flow”与”flight”求最大公共前缀得到”fl”。

  1. class Solution:
  2.     def longestCommonPrefix(self, strs: List[str]) -> str:
  3.         if not strs:
  4.             return ""
  6.         prefix, num = strs[0], len(strs)
  7.         for i in range(1, num):
  8.             prefix = self.lcp(prefix, strs[i])
  9.             if not prefix:
  10.                 break
  12.         return prefix
  14.     def lcp(self, str1, str2):
  15.         length, index = min(len(str1), len(str2)), 0
  16.         while index < length and str1[index] == str2[index]:
  17.             index += 1
  18.         return str1[:index]

时间复杂度：14. 最长公共前缀 - 图3，其中 mm 是字符串数组中的字符串的平均长度，nn 是字符串的数量。最坏情况下，字符串数组中的每个字符串的每个字符都会被比较一次。
空间复杂度：14. 最长公共前缀 - 图4

官方还提供了分治，二分查找的解题思路：
https://leetcode-cn.com/problems/longest-common-prefix/solution/zui-chang-gong-gong-qian-zhui-by-leetcode-solution/