当前位置: 首页 > news >正文

LeetCode--014--最长公共前缀

问题描述:

编写一个函数来查找字符串数组中的最长公共前缀。

如果不存在公共前缀,返回空字符串 ""

示例 1:

输入: ["flower","flow","flight"]
输出: "fl"

示例 2:

输入: ["dog","racecar","car"]
输出: ""
解释: 输入不存在公共前缀。

说明:

所有输入只包含小写字母 a-z 。

方法1:

  贪心:将第一个串和第二个串进行比较,得出的最长前缀再与剩下的进行比较。(48ms)

 1 class Solution(object):
 2     def longestCommonPrefix(self, strs):
 3         """
 4         :type strs: List[str]
 5         :rtype: str
 6         """
 7         if len(strs)>1:
 8             
 9             s0 = strs[0]
10             s1 = strs[1]
11         elif len(strs) == 1:
12             return strs[0]
13         else:
14             return ""
15         common = ""
16         flag = True
17         i = 0
18         while flag and i < len(s0) and i < len(s1):
19             if s0[i] == s1[i]:
20                 common += s0[i]
21             else:
22                 flag = False
23             i += 1
24         for i in range (2,len(strs)):
25             c = strs[i]
26             j = 0
27             common2 = ""
28             while j < len(c) and j < len(common):
29                 if c[j] == common[j]:
30                     common2 += c[j]
31                     j += 1
32                 else:
33                     break
34             common = common2
35         return common

方法2(官方):

  利用min和max函数,找出List中最小值元素s1和最大值元素s2,纪录s1中和s2字符不相同时候的下标,进行截断处理。(24ms)

1 if not len(strs):
2   return ''
3 s1 = min(strs)
4 s2 = max(strs)
5 for n, s in enumerate(s1):
6   if not s2[n] == s:
7       return s1[:n]
8 return s1

注:enumerate() 函数用于将一个可遍历的数据对象(如列表、元组或字符串)组合为一个索引序列,同时列出数据和数据下标,一般用在 for 循环当中。

>>>seasons = ['Spring', 'Summer', 'Fall', 'Winter']
>>> list(enumerate(seasons))
[(0, 'Spring'), (1, 'Summer'), (2, 'Fall'), (3, 'Winter')]
>>> list(enumerate(seasons, start=1))       # 小标从 1 开始
[(1, 'Spring'), (2, 'Summer'), (3, 'Fall'), (4, 'Winter')]
>>>seq = ['one', 'two', 'three']
>>> for i, element in enumerate(seq):
...     print i, element
... 
0 one
1 two
2 three

方法3:

1         ans = ""
2         
3         for i in zip(*strs):
4             if  len(set(i)) > 1:
5                 return ans
6             ans += i[0]
7         
8         return ans
9     

strs=["flower","flgdcvghyf","fove"]
for i in zip(*strs):
     print(i)

>>
('f','f','f')
('l','l','o')
('o','g','v')
('w','d','e')

 

 

2018-07-22 11:18:24

转载于:https://www.cnblogs.com/NPC-assange/p/9349591.html

相关文章:

  • 串口超时处理原理及实现
  • ACM北大暑期课培训第一天
  • Delphi窗体创建释放过程及单元文件小结(转)
  • Linux部署zabbix3.4 结合钉钉智能报警
  • 学生分数排序
  • zabbix3.4上简单web监测功能测试
  • linux系统man查询命令等级与意义
  • 关于ES6的Promise的使用深入理解
  • P1065 津津的储蓄计划
  • 2018年 7月总结8月计划
  • Proteus仿真_01、 8086 IO译码仿真
  • CentOS 7之Postfix部署系列 (二) CentOS网络设置
  • AJAX PHP 请求实例
  • 使用Formik轻松开发更高质量的React表单(二)使用指南
  • HDU-3874 Necklace 线段树+离线
  • 0x05 Python数据分析,Anaconda八斩刀
  • CSS中外联样式表代表的含义
  • ES10 特性的完整指南
  • JavaWeb(学习笔记二)
  • Java到底能干嘛?
  • webpack入门学习手记(二)
  • 从地狱到天堂,Node 回调向 async/await 转变
  • 多线程事务回滚
  • 更好理解的面向对象的Javascript 1 —— 动态类型和多态
  • 基于OpenResty的Lua Web框架lor0.0.2预览版发布
  • 如何打造100亿SDK累计覆盖量的大数据系统
  • 实战|智能家居行业移动应用性能分析
  • 腾讯大梁:DevOps最后一棒,有效构建海量运营的持续反馈能力
  • 无服务器化是企业 IT 架构的未来吗?
  • 小程序 setData 学问多
  • 在GitHub多个账号上使用不同的SSH的配置方法
  • (145)光线追踪距离场柔和阴影
  • (Redis使用系列) Springboot 使用redis实现接口Api限流 十
  • (紀錄)[ASP.NET MVC][jQuery]-2 純手工打造屬於自己的 jQuery GridView (含完整程式碼下載)...
  • (转)Mysql的优化设置
  • (转载)PyTorch代码规范最佳实践和样式指南
  • ... fatal error LINK1120:1个无法解析的外部命令 的解决办法
  • .Net Winform开发笔记(一)
  • .net 程序 换成 java,NET程序员如何转行为J2EE之java基础上(9)
  • .NET/C# 在代码中测量代码执行耗时的建议(比较系统性能计数器和系统时间)...
  • :O)修改linux硬件时间
  • @ModelAttribute注解使用
  • [ 数据结构 - C++] AVL树原理及实现
  • [ 隧道技术 ] 反弹shell的集中常见方式(二)bash反弹shell
  • [CSS]浮动
  • [Gradle] 在 Eclipse 下利用 gradle 构建系统
  • [IE编程] 如何编程清除IE缓存
  • [Java][Android][Process] ProcessBuilder与Runtime差别
  • [LuoguP1141]01迷宫
  • [NOSQL] Redis介绍
  • [毕设]基于STM32的语音识别智能蓝牙音箱设计
  • [翻译] GiFHUD
  • [改善Java代码]非稳定排序推荐使用List
  • [免費軟體] 用15個「免費正版軟體」取代盜版軟體! (狂省10萬元!)
  • [译] 探索 Swift 4 中新的 String API