题目:
编写一个函数来查找字符串数组中的最长公共前缀。如果不存在公共前缀,返回空字符串 ""
。
思路A:横向/纵向扫描
Python:
class Solution:
def longestCommonPrefix(self, strs: List[str]) -> str:
s = ""
if len(strs)<2:
return strs[0]
for i in range(len(strs[0])):
c = strs[0][i]
for j in range(1,len(strs)):
if i>=len(strs[j]) or c!=strs[j][i]:
return s
s+=c
return s
思路B:分治/二分
对于问题 ,可以分解成两个子问题 与 ,其中 。对两个子问题分别求解,然后对两个子问题的解计算最长公共前缀,即为原问题的解。
最长公共前缀的长度不会超过字符串数组中的最短字符串的长度。可以在 [0,minLength] 的范围内通过二分查找得到最长公共前缀的长度。每次取查找范围的中间值 mid,判断每个字符串的长度为 mid 的前缀是否相同,如果相同则最长公共前缀的长度一定大于或等于 mid,如果不相同则最长公共前缀的长度一定小于 mid,通过上述方式将查找范围缩小一半,直到得到最长公共前缀的长度。
Python:
class Solution:
def longestCommonPrefix(self, strs: List[str]) -> str:
def lcp(start, end):
if start == end:
return strs[start]
mid = (start + end) // 2
lcpLeft, lcpRight = lcp(start, mid), lcp(mid + 1, end)
minLength = min(len(lcpLeft), len(lcpRight))
for i in range(minLength):
if lcpLeft[i] != lcpRight[i]:
return lcpLeft[:i]
return lcpLeft[:minLength]
return "" if not strs else lcp(0, len(strs) - 1)
class Solution:
def longestCommonPrefix(self, strs: List[str]) -> str:
def isCommonPrefix(length):
str0, count = strs[0][:length], len(strs)
return all(strs[i][:length] == str0 for i in range(1, count))
if not strs:
return ""
minLength = min(len(s) for s in strs)
low, high = 0, minLength
while low < high:
mid = (high - low + 1) // 2 + low
if isCommonPrefix(mid):
low = mid
else:
high = mid - 1
return strs[0][:low]