【Leetcode】【简单】【14最长公共前缀】【JavaS…
2019-03-10 11:52:45来源:博客园 阅读 ()
题目
14. 最长公共前缀
编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀,返回空字符串
""
。示例 1:
输入: ["flower","flow","flight"] 输出: "fl"示例 2:
输入: ["dog","racecar","car"] 输出: "" 解释: 输入不存在公共前缀。说明:
所有输入只包含小写字母
a-z
。
解答
解答一:两层for循环
误区1:刚开始考虑了先数组元素遍历,然后再元素(字符串)从头到尾比较,但实际上要先以第一个元素strs[0]为基准。
漏洞1:没有考虑strs元素为空字符串的情况,如[""],未考虑连续元素都相等的情况如["c","c"],结果这些在提交时都是要判断的。
个人思路:
1、若传入为空数组[]或空字符串[""]则直接返回空字符串;
2、取传入数组的第一个元素为基准字符串,并声明common数组,用于存放公共前缀;
3、第一层i循环(可以想像指针指向strs[0],且从strs[0][0]往str[0][1、2、3…]移动),第二层j循环(可以想像指针指向strs[1],且从strs[1]往str[2、3…]移动),即题中"flower"中的"f",与"flow"中的"f"相比较;
4、相同则j自增,即"flower"中的"f"继续与"flight"中的"f"比较;
5、若j循环未彻底完成,即说明当前的str[i]已经不是公共前缀了,就可以返回common了;若此次j循环彻底完成,则将当前的str[i],push进common;
6、外层的i循环结束后,若未触发过j循环内的return的话,类似["a","a","a"]["ab","abc","abcd"]等等情况的,直接返回strs[0],即str即可。
代码如下:(已在leetcode提交通过,执行用时104ms)
var longestCommonPrefix = function(strs) { if (strs.length===0 ||strs[0].length===0){return "";} var str=strs[0], common=[]; for(let i=0,len1=str.length;i<len1;i++){ for(let j=1,len2=strs.length;j<len2;j++){ if(str[i]!==strs[j][i]){ return common.join(""); } } common.push(str[i]); }return str; };
两层循环示意图如下:
(GIF)
解答二:水平扫描法
参考平台提供题解,提供的第一种方法是“水平扫描法”:
仍然是先把数组中第一个元素str取出来,然后以这个元素为基准,
使用stringObject.indexOf(searchvalue,fromindex)方法查找,
查一下str是否在strs[i]索引为0的位置,
如果不在索引为0的位置,使用stringObject.substring(start,stop)删减字符串长度,
把str长度减1,再继续查,直到str长度减到0为止。
代码如下:(已在leetcode提交通过,执行用时100ms)
var longestCommonPrefix = function(strs) { if (strs.length===0 ||strs[0].length===0){return "";} var str=strs[0]; for (let i=1,len=strs.length;i<len;i++){ while(strs[i].indexOf(str)!==0) { if (str.length === 0) {return "";} str = str.substring(0, str.length - 1); } }return str; }
public String longestCommonPrefix(String[] strs) { if (strs.length == 0) return ""; String prefix = strs[0]; for (int i = 1; i < strs.length; i++) while (strs[i].indexOf(prefix) != 0) { prefix = prefix.substring(0, prefix.length() - 1); if (prefix.isEmpty()) return ""; } return prefix; }
平台提供示意图如下:
解答三:水平扫描法(改良)
参考平台提供题解,水平扫描法有改良版,
不是取数组第一个元素,还是直接取该元素中的单独字符,类似本页中第一种方法,两个for循环,代码稍有区别。
首先第一层for循环(枚举首个字符串的所有字符),使用stringObject.charAt(index)方法获取数组第一个元素的第i个字符,赋值给c,
第二层for循环,从索引1开始遍历数组中所有剩余元素的对应i位置的字符,并与c比较,
如果该字符不等于c,或者压根没有该字符,直接使用stringObject.substring(start,stop)方法返回首个元素从索引0到i的拷贝,
若两层循环都正常运行过,未触发返回,则是类似["ab","abc","abcd"]["aa",aaa"","aaaaa"]这些情况,即第一个元素最短,且整体都符合条件,此时返回这个元素即可。
代码如下:(已在leetcode提交通过,执行用时92ms)
var longestCommonPrefix = function(strs) { if (strs.length===0 ||strs[0].length===0){return "";} for (let i=0,len1=strs[0].length;i<len1;i++){ let c=strs[0].charAt(i); for (let j=1,len2=strs.length;j<len2;j++){ if(i===strs[j].length||strs[j].charAt(i)!==c){ return strs[0].substring(0,i); } } }return strs[0]; }
插
插
插
原文链接:https://www.cnblogs.com/2463901520-sunda/p/10498955.html
如有疑问请与原作者联系
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- JS简单去除数组中重复项的方法 2020-03-16
- JS判断浏览器是否安装flash插件的简单方法 2020-03-12
- JavaScript简单下拉菜单特效 2020-02-22
- Js操作DOM元素及获取浏览器高宽的简单方法 2019-12-31
- JS简单随机数生成方法 2019-12-29
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash