IT评测·应用市场-qidao123.com

标题: python：编写一个函数查找字符串中的最长公共前缀 [打印本页]
作者: 知者何南    时间: 2024-9-27 10:57
标题: python：编写一个函数查找字符串中的最长公共前缀
最近在csdn网站上刷到一个题目，题目要求编写一个函数查找字符串中的最长公共前缀，题目如下：

给出的答案如下：
  1. from typing import List
  2. def longestCommonPrefix(strs:List[str]) -> str:
  3.         if len(strs) == 0:
  4.                 return ''
  5.         i = 0     #代表公共前缀的位数
  6.         lcp = []  #存放公共前缀
  7.         while True:
  8.                 done = False
  9.                 if  i >= len(strs[0]):
  10.                         break
  11.                 j = 0   #代表strs列表中的元素个数，依次对元素做比较
  12.                 while j < len(strs):
  13.                         if i < len(strs[j]):
  14.                                 if strs[j][i] != strs[0][i]:
  15.                                         done  = True
  16.                                         break
  17.                         else:
  18.                                 done = True
  19.                                 break
  20.                         j+=1
  22.                 if not done:
  23.                         lcp.append(strs[0][i])
  24.                         i+=1
  25.                 else:
  26.                         break
  27.         return ''.join(lcp)
复制代码
乍一看确实有些复杂了，但是思路也还比较清晰：
利用列表中的第1个元素作为比较对象，依次对比第1个元素中的每1位字符是否与其他元素的该位置的字符一致，如果一致就参加到新的列表，遇到不一致的就break退出，最后通过字符串的join方法返回公共前缀。
  1. strs = ['flower','flow','flight','flue']
  2. print(f'公共前缀：{longestCommonPrefix1(strs)}')
  3. #结果
  4. fl
复制代码
我们可以改良下代码，看上去更好理解，处置惩罚思路如下：
先获取给定列表中的最短的元素，在该元素的基础上循环检查其他元素的每一个位是否相同，相同就参加新的列表，遇到不一致的就break退出，最后通过字符串的join方法返回公共前缀。
主要改造阐明：
1）利用sorted函数将列表按照元素length从小到达分列，获取到最短的元素
2）利用列表推导式挨个获取相同位置的元素，如果是一样的，颠末集合转换后，只会保留1个元素（集合是不重复的元素，可以达到去重功能）
改良的函数如下：
  1. def longestCommonPrefix1(strs:List[str]) -> str:
  2.         if len(strs) == 0:
  3.                 return ''
  4.         #使用sorted函数将列表按照元素length从小到达排列，获取到最短的元素new_strs[0]
  5.         new_strs = sorted(strs,key=lambda x:len(x),reverse=False)
  6.         print(new_strs)
  7.         lcp = []  #存放公共前缀
  8.   #使用range函数循环处理最短元素length
  9.         for i  in range(len(new_strs[0])):
  10.           #使用列表推导式挨个获取相同位置的元素，如果是一样的，
  11.     #经过集合转换后，只会保留1个元素（集合是不重复的元素，可以达到去重功能）
  12.                 if len(set([j[i] for j in new_strs ])) == 1:
  13.                         lcp.append(new_strs[0][i])
  14.                 else:
  15.                         break
  16.         return ''.join(lcp)
复制代码
  1. strs = ['flower','flow','flight','flue']
  2. print(f'公共前缀：{longestCommonPrefix1(strs)}')
  3. strs = ['flower','flow','flight','dlue']
  4. print(f'公共前缀：{longestCommonPrefix1(strs)}')
  5. #结果：
  6. ['flow', 'flue', 'flower', 'flight']
  7. 公共前缀：fl
  8. ['flow', 'dlue', 'flower', 'flight']
  9. 公共前缀：
复制代码
不知道大家另有什么方法，请评论区指教。

共勉： 东汉·班固《汉书·枚乘传》：“泰山之管穿石，单极之绠断干。水非石之钻，索非木之锯，渐靡使之然也。”
-----指水滴不断地滴，可以滴穿石头；
-----比喻坚持不懈，集渺小的力量也能成就难能的功劳。
----感谢读者的阅读和学习，谢谢大家。

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。



欢迎光临 IT评测·应用市场-qidao123.com (https://dis.qidao123.com/) Powered by Discuz! X3.4