首页 > 编程语言 > 详细

LeetCode第[14]题(Java): Longest Common Prefix

时间:2018-04-21 23:09:48      阅读:67      评论:0      收藏:0      [点我收藏+]

标签:答案   问题   保存   pub   buffer   i+1   效应   字符串数组   null   

题目:最长公共前缀

难度:EASY

题目内容

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:

所有输入都是小写字母a-z。

 

我的思路:最简单的方法对String[]中最短的那一个长度进行遍历,在遍历中取String[]中每一个的当前位置字符与下一个比较,一旦不一样就返回结果。

     还有一种就是,用Set,在内部遍历中用set将String[]中每一个的当前位置字符放入,出来的时候判断size()是否==1,好吧这种空间复杂度更高,显得更蠢。。

 1     public String longestCommonPrefix(String[] strs) {
 2         if (strs.length < 1) {
 3             return "";
 4         }
 5         
 6         int minlen = Integer.MAX_VALUE;
 7         for (int i = 0;i < strs.length; i++) {
 8             if (strs[i].length() < minlen) {
 9                 minlen = strs[i].length();
10             }
11         } // 获得最短长度minLen
12         
13         
14         StringBuffer sb = new StringBuffer();
15         for (int j = 0; j < minlen; j++) {
16             for (int i = 0; i< strs.length - 1; i++) {
17                 if (strs[i].charAt(j) != strs[i+1].charAt(j)) {
18                     return sb.toString();
19                 }
20             }
21             sb.append(strs[0].charAt(j));
22         }
23         return sb.toString();
24     }

我的时间复杂度:  O(N*M)   N为字符串个数,M最短字符串长度

编码过程问题
1、一开始直接拿strs[0]的长度做的循环,导致测试用例{aa,a}越界,写了minLen后通过

2、minLen的初值一开始写成了MIN_VALUE.

 

参考答案Code:

1     public String longestCommonPrefix(String[] strs) {
2         if (strs == null || strs.length == 0)
3             return "";
4         String pre = strs[0];
5         for (int i = 1; i < strs.length; i++)
6             while (strs[i].indexOf(pre) != 0) 
7                 pre = pre.substring(0, pre.length()-1);
8         return pre;
9     }

9行! 厉害了,。。

答案复杂度:O(N*M)   虽然复杂度看起来一样,但是其实每次while循环并没有循环M次,也少了取minLen的操作

答案思路:取任意一个字符串做初始前缀,然后对后面每一个进行while循环:如果当前的前缀 与你进行字符串匹配的结果不是0【是0则是前缀,null,和其他字符都不行】,则把pre的最后一个字符去掉,再匹配,直到为0.

由于是取大家最长的公共前缀,所以也就类似于木桶短板效应,最后的值会是那个最短的,所以把pre保存给下一个再进行while循环。

 

LeetCode第[14]题(Java): Longest Common Prefix

标签:答案   问题   保存   pub   buffer   i+1   效应   字符串数组   null   

原文:https://www.cnblogs.com/Xieyang-blog/p/8904153.html

(0)
(0)
   
举报
评论 一句话评论(0
0条  
登录后才能评论!
© 2014 bubuko.com 版权所有 鲁ICP备09046678号-4
打开技术之扣,分享程序人生!
             

鲁公网安备 37021202000002号