python：编写一个函数查找字符串中的最长公共前缀

最近在csdn网站上刷到一个题目，题目要求编写一个函数查找字符串中的最长公共前缀，题目如下：

给出的答案如下：

from typing import List
def longestCommonPrefix(strs:List[str]) -> str:
if len(strs) == 0:
return ''
i = 0     #代表公共前缀的位数
lcp = []  #存放公共前缀
while True:
done = False
if  i >= len(strs[0]):
break
j = 0   #代表strs列表中的元素个数，依次对元素做比较
while j < len(strs):
if i < len(strs[j]):
if strs[j][i] != strs[0][i]:
done  = True
break
else:
done = True
break
j+=1

if not done:
lcp.append(strs[0][i])
i+=1
else:
break
return ''.join(lcp)

乍一看确实有些复杂了，但是思路也还比较清晰：

使用列表中的第1个元素作为比较对象，依次对比第1个元素中的每1位字符是否与其他元素的该位置的字符一致，如果一致就加入到新的列表，遇到不一致的就break退出，最后通过字符串的join方法返回公共前缀。

strs = ['flower','flow','flight','flue']
print(f'公共前缀：{longestCommonPrefix1(strs)}')
#结果
fl

我们可以改良下代码，看上去更好理解，处理思路如下：

先获取给定列表中的最短的元素，在该元素的基础上循环检查其他元素的每一个位是否相同，相同就加入新的列表，遇到不一致的就break退出，最后通过字符串的join方法返回公共前缀。

主要改造说明：

1）使用sorted函数将列表按照元素length从小到达排列，获取到最短的元素

2）使用列表推导式挨个获取相同位置的元素，如果是一样的，经过集合转换后，只会保留1个元素（集合是不重复的元素，可以达到去重功能）

改良的函数如下：

def longestCommonPrefix1(strs:List[str]) -> str:
if len(strs) == 0:
return ''
#使用sorted函数将列表按照元素length从小到达排列，获取到最短的元素new_strs[0]
new_strs = sorted(strs,key=lambda x:len(x),reverse=False)
print(new_strs)
lcp = []  #存放公共前缀
  #使用range函数循环处理最短元素length
for i  in range(len(new_strs[0])):
  #使用列表推导式挨个获取相同位置的元素，如果是一样的，
    #经过集合转换后，只会保留1个元素（集合是不重复的元素，可以达到去重功能）
if len(set([j[i] for j in new_strs ])) == 1:
lcp.append(new_strs[0][i])
else:
break
return ''.join(lcp)

strs = ['flower','flow','flight','flue']
print(f'公共前缀：{longestCommonPrefix1(strs)}')
strs = ['flower','flow','flight','dlue']
print(f'公共前缀：{longestCommonPrefix1(strs)}')
#结果：
['flow', 'flue', 'flower', 'flight']
公共前缀：fl
['flow', 'dlue', 'flower', 'flight']
公共前缀：

不知道大家还有什么方法，请评论区指教。

共勉： 东汉·班固《汉书·枚乘传》：“泰山之管穿石，单极之绠断干。水非石之钻，索非木之锯，渐靡使之然也。”

-----指水滴不断地滴，可以滴穿石头；

-----比喻坚持不懈，集细微的力量也能成就难能的功劳。

----感谢读者的阅读和学习，谢谢大家。

原文地址：https://blog.csdn.net/kymppcds/article/details/142427241

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！