题目
编写一个函数来查找字符串数组中的最长公共前缀。如果不存在公共前缀，返回空字符串 ‘’
例子
- [“flower”,”flow”,”flight”] -> ‘fl’
- [“dog”,”racecar”,”car”] -> ‘’
假设
- 输入的字符串一定不为None或空串
- 输入的字符串中的字符仅为小写英文字母
tips
- 找出前两个字符串的最长公共前缀
- 找1中最长公共前缀和下一个串的最长公共前缀
- 继续找上一个最长公共前缀和下一个串最长公共前缀
答案
解法1:
def longestCommonPrefix(strs: List[str]):
if not strs:
return ""
prefix, count = strs[0], len(strs)
for i in range(1, count):
prefix = self.lcp(prefix, strs[i])
if not prefix:
break
return prefix
def lcp(str1, str2):
length, index = min(len(str1), len(str2)), 0
while index < length and str1[index] == str2[index]:
index += 1
return str1[:index]
性能
- 时间复杂度O(mn)
- 空间复杂度O(1)
关键点
1.找出前两个字符串的最长公共前缀
2.找1中最长公共前缀和下一个串的最长公共前缀
3.继续找上一个最长公共前缀和下一个串的最长公共前缀
算法描述
- 将第一个字符串作为前缀，和第二个比较，返回公共前缀
- 遍历字符串，返回公共前缀和后一个字符的公共部分
- 木桶原则，以最短的部分作为最长公共前缀
算法2：
def longestCommonPrefix(strs):
"""
:param strs:
:return:
"""
base = strs[0] # 前缀池
prefix = base[0] # 前缀
base = base[1:]
flag = 0 # 字符串计数器
while True:
# 遍历列表中的字符串是否都是以prefix为前缀，使用flag计数
for item in strs:
if item.startswith(prefix):
flag += 1
if flag == len(strs):
# 如果计数器和列表长度相同，则增加前缀长度
# 如果第一个字符串是列表中最短字符串时，会发生越界
try:
prefix += base[0]
base = base[1:]
except IndexError as e:
return prefix
flag = 0
else:
return prefix[:-1]性能
- 时间复杂度O(mn)
- 空间复杂度O(n)
关键点
- 利用报错判断
- 利用startwith()判断字符串是否以某个字符串开头
算法描述
- 选择第一个字符串作为前缀选择池
- 使用前缀选择池的第一个字符作为前缀判断其他字符串是否以此开头
- 然后依次将第一个字符串后面的字符加入
- 当flag小于字符串数量时返回前缀，需要删除前缀的最后一个字符，因为最后一个字符加入后才导致计数器小于字符串数量，所以最后一个字符不属于公共前缀
- 当第一个字符串是列表中字符串长度最短的时，会发生下标越界，此时利用except捕捉错误并返回前缀
算法3：
from functools import reduce
def longestCommonPrefix(strs):
def findCommonPrefix(s1, s2):
prefix = ''
for i in range(min(len(s1), len(s2))):
if s1[i] == s2[i]:
prefix += s1[i]
else:
return prefix
return prefix
return reduce(findCommonPrefix, strs)性能
- 时间复杂度O(nlogn)
- 空间复杂度O(1)
关键点
1.算法1的reduce实现
算法描述
- 将第一个字符串作为前缀，和第二个比较，返回公共前缀
- 遍历字符串，返回公共前缀和后一个字符的公共部分
- 木桶原则，以最短的部分作为最长公共前缀