最近在csdn网站上刷到一个题目,题目要求编写一个函数查找字符串中的最长公共前缀,题目如下:
给出的答案如下:
from typing import List
def longestCommonPrefix(strs:List[str]) -> str:if len(strs) == 0:return ''i = 0 #代表公共前缀的位数lcp = [] #存放公共前缀while True:done = Falseif i >= len(strs[0]):breakj = 0 #代表strs列表中的元素个数,依次对元素做比较while j < len(strs):if i < len(strs[j]):if strs[j][i] != strs[0][i]:done = Truebreakelse:done = Truebreakj+=1if not done:lcp.append(strs[0][i])i+=1else:breakreturn ''.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函数循环处理最短元素lengthfor 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:breakreturn ''.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']
公共前缀:
不知道大家还有什么方法,请评论区指教。
共勉: 东汉·班固《汉书·枚乘传》:“泰山之管穿石,单极之绠断干。水非石之钻,索非木之锯,渐靡使之然也。”
-----指水滴不断地滴,可以滴穿石头;
-----比喻坚持不懈,集细微的力量也能成就难能的功劳。
----感谢读者的阅读和学习,谢谢大家。