# Leetcode 14:Longest Common Prefix 最长公共前缀
公众号:爱写bug
Write a function to find the longest common prefix string amongst an array of strings.
If there is no common prefix, return an empty string ""
.
编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀,返回空字符串 ""
。
Example 1:
Input: ["flower","flow","flight"] Output: "fl"
Example 2:
Input: ["dog","racecar","car"] Output: "" Explanation: There is no common prefix among the input strings.
Note:
All given inputs are in lowercase letters a-z
.
说明:
所有输入只包含小写字母 a-z
。
解题思路Java:
很简单又很经典的一道题,我的思路起先是 把第字符串组第一个字符串转为char型。利用StringBuilder逐一累加相同字符。由于字符串长度不一,可以先遍历找出最小长度字符串,这里我选择抛错的形式,减少一次遍历。
代码:
class Solution { public String longestCommonPrefix(String[] strs) { int strLen=strs.length; if(strLen==0) return "";//空字符串组返回"" char[] temp=strs[0].toCharArray(); StringBuilder str = new StringBuilder(); for (int i=0;i<strs[0].length();i++){//以第一个字符串长度开始比较 for (int j=1;j<strLen;j++){ try { if(temp[i]!=strs[j].charAt(i)){ return str.toString(); } }catch (IndexOutOfBoundsException e){//抛出错误,这里错误是指索引超出字符串长度 return strs[j]; } } str.append(temp[i]); } return strs[0]; } }
后面想到Java有 subString()
方法,可指定长度截取字符串,无需转为 char[]
型,但是在 Leetcode 提交时反而不如上面这种方式运算快,这也说明了Java不支持运算符重载,使用 substring()
每次新建一个String字符串,效率并不高。
最后看到一个方法,大致思路是找到最小长度字符串,从大到小截取字符串,既然用到 subString()
方法,不如就从后向前,因为题目是找出最长公众前缀,从大到小效率很高。具体请看:
public class Solution { public String longestCommonPrefix(String[] strs) { if(strs.length==0) return ""; int min=Integer.MAX_VALUE; String minStr=""; for(int i=0;i<strs.length;i++){//找出最小长度字符串 if(min>strs[i].length()){ minStr=strs[i]; min=strs[i].length(); } } if(min==0) return ""; for(int i=min;i>=0;i--){//最小长度字符串从长到短截取 String standard=minStr.substring(0, i); int j=0; for(j=0;j<strs.length;j++){ if(strs[j].substring(0, i).equals(standard)) continue; else break; } if(j==strs.length) return standard; } return ""; } }
原代码链接: https://blog.csdn.net/qq_14927217/article/details/72955791
解题思路py3:
再次投机取巧,os.path 封装函数 commonprefix()
一步到位。
代码:
class Solution(object): def longestCommonPrefix(self, strs): import os return os.path.commonprefix(strs)
其实该函数是利用ASCll码比较的特性来编写的,源码:
def commonprefix(m): "Given a list of pathnames, returns the longest common leading component" if not m: return '' # Some people pass in a list of pathname parts to operate in an OS-agnostic # fashion; don't try to translate in that case as that's an abuse of the # API and they are already doing what they need to be OS-agnostic and so # they most likely won't be using an os.PathLike object in the sublists. if not isinstance(m[0], (list, tuple)): m = tuple(map(os.fspath, m)) s1 = min(m) s2 = max(m) for i, c in enumerate(s1)://枚举得到s1的每一个字符及其索引 if c != s2[i]: return s1[:i] return s1
尽管如此,py3这段代码的执行速度依然远比Java慢的多。
注:ASCll码比较大小并非是按照所有字符的ASCll累加之和比较,是从一个字符串第一个字符开始比较大小,如果不相同直接得出大小结果,后面的字符不在比较。
低调大师中文资讯倾力打造互联网数据资讯、行业资源、电子商务、移动互联网、网络营销平台。
持续更新报道IT业界、互联网、市场资讯、驱动更新,是最及时权威的产业资讯及硬件资讯报道平台。
转载内容版权归作者及来源网站所有,本站原创内容转载请注明来源。
- 上一篇
SpringBoot使用WebSocket(一)
webSocket是HTML5的一种新协议,它实现了服务端与客户端的全双工通信,建立在传输层,tcp协议之上,即浏览器与服务端需要先建立tcp协议,再发送webSocket连接建立请求。webSocket的连接:客户端发送请求信息,服务端接受到请求并返回相应的信息。连接建立。客户端发送http请求时,通过 Upgrade:webSocket Connection:Upgrade 告知服务器需要建立的是webSocket连接,并且还会传递webSocket版本号,协议的字版本号,原始地址,主机地址, webSocket相互通信的Header很小,大概只有2Bytes 本文介绍SpringBoot结合WebSocket的实现群发消息,如想学习如何一对一发送消息可前往查看第二篇springboot使用websocket(二) 1. 导入依
- 下一篇
白盒测试快速入门1-简介
什么是白盒测试? 白盒测试被定义为测试软件解决方案的内部结构,设计和编码。在这种类型的测试中,代码对测试人员是可见的。它主要侧重于通过应用程序验证输入和输出的流程,改进设计和可用性,加强安全性。白盒测试也称为透明盒测试,开箱测试,结构测试,基于代码的测试和玻璃盒测试。它通常由开发人员执行。 它是软件测试“盒子测试”方法的两个部分之一。其对应的黑盒测试涉及从外部或最终用户类型的角度进行测试。另一方面,白盒测试基于应用程序的内部工作,并围绕内部测试。 由于透视框概念,使用了术语“WhiteBox”。透明框或WhiteBox名称表示能够透过软件的外壳(或“盒子”)进入其内部工作。同样,“黑匣子测试”中的“黑匣子”表示无法看到软件的内部工作方式,因此只能测试最终用户体验。 白盒测试中验证什么? 白盒测试涉及测试以下软件代码: 内部安全漏洞 编码过程中的路径损坏或结构不良 特定输入流 预期输出 条件循环 单独测试每个语句,对象和函数 测试可以在系统,集成和单元级别的软件开发中完成。白盒测试的基本目标之一是验证应用程序的工作流程。它涉及针对预期或期望的输出测试一系列预定义输入。 如果视频无法访...
相关文章
文章评论
共有0条评论来说两句吧...
文章二维码
点击排行
推荐阅读
最新文章
- CentOS8编译安装MySQL8.0.19
- CentOS7,8上快速安装Gitea,搭建Git服务器
- CentOS6,7,8上安装Nginx,支持https2.0的开启
- CentOS关闭SELinux安全模块
- SpringBoot2初体验,简单认识spring boot2并且搭建基础工程
- SpringBoot2整合MyBatis,连接MySql数据库做增删改查操作
- CentOS8安装MyCat,轻松搞定数据库的读写分离、垂直分库、水平分库
- CentOS8安装Docker,最新的服务器搭配容器使用
- CentOS7,CentOS8安装Elasticsearch6.8.6
- Red5直播服务器,属于Java语言的直播服务器