发布于2019-08-07 18:31 阅读(364) 评论(0) 点赞(0) 收藏(3)
编写一个函数来查找字符串数组中的最长公共前缀。 如果不存在公共前缀,返回空字符串 ""。 示例 1: 输入: ["flower","flow","flight"] 输出: "fl" 示例 2: 输入: ["dog","racecar","car"] 输出: "" 解释: 输入不存在公共前缀。 说明: 所有输入只包含小写字母 a-z 。
这题比较好理解,给定一个列表,查询列表中的公共前缀
自己的想法是直接暴力法解决,将列表的第一个值作为对比值,通过一层for循环不断遍历对比值与其他元素是否相等,如果相等则继续对比,如果不等return比较过的值。
上代码(40ms)击败12%用户
1 class Solution(object): 2 def longestCommonPrefix(self, strs): 3 """ 4 :type strs: List[str] 5 :rtype: str 6 """ 7 sig=True 8 i=0 9 if(strs==[] ): #判断是否为空 10 return "" 11 if(len(strs)==1): #判断是否只有一个值 12 return strs[0] 13 if ("" in strs): #判断有没有空值 14 return "" 15 while(sig==True ): #sig是一个bool类型值 True继续判断 False中断返回 16 if(len(strs[0])<=i): #判断对比值是否越界 17 return strs[0][0:i] 18 temp=strs[0][i] #第i个字符 19 for j in strs[1:]: 20 if(temp!=j[i] ): #如果第i字符不匹配 则返回前i-1个字符 21 return strs[0][0:i] 22 elif(temp==j[i] and len(j)==i+1): #如果第i字符为最后一个一字母,则不继续对比,返回前i个 23 sig=False 24 k=i 25 i += 1 26 return strs[0][0:k+1] 27 if __name__=="__main__": 28 s=Solution() 29 li=["flower","flo","flight"] 30 print(s.longestCommonPrefix(li))
看了评论区大佬的代码,觉得有一个想法特别好
上代码(28ms)击败94%
1 class Solution(object): 2 def longestCommonPrefix(self, strs): 3 """ 4 :type strs: List[str] 5 :rtype: str 6 """ 7 if not strs: return "" 8 if len(strs) == 1: return strs[0] 9 10 strs.sort() 11 p = '' 12 for x, y in zip(strs[0], strs[-1]): 13 if x == y: 14 p += x 15 else: 16 break 17 return p 18 if __name__=="__main__": 19 s=Solution() 20 li=["flower","fl","flight"] 21 print(s.longestCommonPrefix(li))
解释一下:
前两句没啥好说的,判断特殊情况
然后进行排序,直接将第一个元素和最后一个元素对比,提取出相同字符。
特点:排序后的列表,不需要对比中间的元素 直接对比最后两个即可。
作者:就是这么自信
链接:https://www.pythonheidong.com/blog/article/12119/e0a93f40efe85476ca75/
来源:python黑洞网
任何形式的转载都请注明出处,如有侵权 一经发现 必将追究其法律责任
昵称:
评论内容:(最多支持255个字符)
---无人问津也好,技不如人也罢,你都要试着安静下来,去做自己该做的事,而不是让内心的烦躁、焦虑,坏掉你本来就不多的热情和定力
Copyright © 2018-2021 python黑洞网 All Rights Reserved 版权所有,并保留所有权利。 京ICP备18063182号-1
投诉与举报,广告合作请联系vgs_info@163.com或QQ3083709327
免责声明:网站文章均由用户上传,仅供读者学习交流使用,禁止用做商业用途。若文章涉及色情,反动,侵权等违法信息,请向我们举报,一经核实我们会立即删除!