题目

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

示例

1. 输入：$strs=["flower","flow","flight"]$
   输出：$“fl"$
2. 输入：$strs=["dog","racecar","car"]$
   输出：$“"$
   解释：输入不存在公共前缀。

思路

1. 纵向扫描

虽然这道题的难度是简单，但是我感觉一点也不简单。大概的想法是将里面的字符串同时依次扫描，然后直到有不同的字符出现为止，最后输出前面相同的字符。虽然想到用二维数组来表示，但是代码能力太差，写不出这个思路。
看了官方答案，原来二维数组就是直接表示，才发现是我之前想复杂了。

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

class Solution:def longestCommonPrefix(self, strs: List[str]) -> str:if not strs:return ""for i in range(len(strs[0])):c = strs[0][i]for j in range(1, len(strs)):# 这里记得要先检查索引 i 是否超出了字符串的范围，再进行字符比较，否则可能会溢出if i == len(strs[j]) or strs[j][i]!= c:return strs[0][:i]return strs[0]

2. 横向扫描

思路为先将列表中的第一个字符串作为最长公共前缀，然后和第二个字符串比较，找出新的最长公共前缀，这个新的再依次和下一个字符串做比较，以此类推。最难想到的应该是怎么比较列表中的两个字符串，然后得到新的公共前缀，可以使用一个新的函数来实现或者继续使用二维数组。

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

# 新建一个函数
class Solution:def longestCommonPrefix(self, strs: List[str]) -> str:if not strs:return ""# 先将第一个字符串当作最长公共前缀same = strs[0]for i in range(1, len(strs)):# 让新的公共前缀和下一个字符相比较same = self.compared(same, strs[i])if not same:breakreturn same# 比较两个字符串，找出最长公共前缀def compared(self, str1, str2):n = min(len(str1), len(str2))index = 0# 直到比较的两个字符不同为止或者 遍历完较短的那个字符串while index < n and str1[index] == str2[index]:index += 1return str1[:index]

# 二维数组
class Solution:def longestCommonPrefix(self, strs: List[str]) -> str:if not strs:return ""# 先将第一个字符串当作最长公共前缀same = strs[0]for i in range(1, len(strs)):n = min(len(same), len(strs[i]))j = 0# 这里我们用二维数组，直接让新的公共前缀和下一个字符串相比较while j < n and same[j] == strs[i][j]:j += 1same = same[:j]if not same:breakreturn same