题目
编写一个函数来查找字符串数组中的最长公共前缀。如果不存在公共前缀，返回空字符串 ''
例子
["flower","flow","flight"] -> 'fl'
["dog","racecar","car"] -> ''
假设
输入的字符串一定不为None或空串
输入的字符串中的字符仅为小写英文字母
tips
找出前两个字符串的最长公共前缀
找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)
我的答案
from functools import reduce
def findCommonPrefixOfTwoString(s1, s2):
n = min(len(s1), len(s2))
i = 0
while i < n:
if s1[i] == s2[i]:
i += 1
else:
break
return s1[:i]
# print(findCommonPrefixOfTwoString('123', '456'))
def longestCommonPrefix(strs):
return reduce(findCommonPrefixOfTwoString, strs)
s1 = ["flower","flow","flight"]
s2 = ["dog","racecar","car"]
print(longestCommonPrefix(s1))
print(longestCommonPrefix(s2))
