Python递归实现最长公共前缀算法
"""
Python递归实现最长公共前缀
"""
def longest_common_prefix(strs):
"""
:type strs: List[str]
:rtype: str
"""
if not strs:
return ""
elif len(strs) == 1:
return strs[0]
def lcp(start, end):
if start == end:
return strs[start]
else:
mid = (start + end)//2
lcp_left = lcp(start, mid)
lcp_right = lcp(mid+1, end)
return common_prefix(lcp_left, lcp_right)
def common_prefix(left, right):
min_len = min(len(left), len(right))
for i in range(min_len):
if left[i] != right[i]:
return left[:i]
return left[:min_len]
return lcp(0, len(strs)-1)
测试代码
print(longest_common_prefix(['pidancode.com', 'pida', 'pidan', 'pidalloween'])) # 'pi'
print(longest_common_prefix(['皮蛋编程', '皮蛋', '皮蛋壳', '皮蛋状'])) # '皮蛋'
相关文章