首页 > 代码库 > Longest Common Prefix leetcode java
Longest Common Prefix leetcode java
题目:
Write a function to find the longest common prefix string amongst an array of strings.
题解:
解题思路是,先对整个String数组预处理一下,求一个最小长度(最长前缀肯定不能大于最小长度)。
然后以第0个字符串作为参照,从第1个字符串到最后一个字符串,对同一位置做判断,有不同字符串返回当前记录的字符串就行。
我的代码如下,不是那么简洁好看,下面有个整理的更好一些:
1 private static int MinLength(String[] strs) {
2 int temp = Integer.MAX_VALUE;
3 for(int i=0; i<strs.length;i++){
4 if(temp>strs[i].length())
5 temp = strs[i].length();
6 }
7 return temp;
8 }
9
10 public static String longestCommonPrefix(String[] strs) {
11 if(strs.length==0){
12 return "";
13 }
14 int j = 0;
15 boolean flag = false;
16
17 int length = MinLength(strs);
18
19 while(j<length){
20 int i = 1;
21 while(i<strs.length){
22 int c = strs[0].charAt(j);
23 if(strs[i].charAt(j)==c){
24 i++;
25 }else{
26 flag = true;
27 break;
28 }
29 }
30 if(flag)
31 break;
32 j++;
33 }
34
35 return strs[0].substring(0, j);
36 }
2 int temp = Integer.MAX_VALUE;
3 for(int i=0; i<strs.length;i++){
4 if(temp>strs[i].length())
5 temp = strs[i].length();
6 }
7 return temp;
8 }
9
10 public static String longestCommonPrefix(String[] strs) {
11 if(strs.length==0){
12 return "";
13 }
14 int j = 0;
15 boolean flag = false;
16
17 int length = MinLength(strs);
18
19 while(j<length){
20 int i = 1;
21 while(i<strs.length){
22 int c = strs[0].charAt(j);
23 if(strs[i].charAt(j)==c){
24 i++;
25 }else{
26 flag = true;
27 break;
28 }
29 }
30 if(flag)
31 break;
32 j++;
33 }
34
35 return strs[0].substring(0, j);
36 }
更简洁的代码:
1 private int minlen(String[] strs) {
2 int min = Integer.MAX_VALUE;
3 for(int i=0; i<strs.length;i++)
4 min = Math.min(min,strs[i].length());
5 return min;
6 }
7
8 public String longestCommonPrefix(String[] strs) {
9 if (strs == null || strs.length == 0)
10 return "";
11
12 StringBuilder res = new StringBuilder();
13 int index = 0;
14 int len = minlen(strs);
15 while (index < len){
16 for (int i=1; i<strs.length;i++){
17 if (strs[i].charAt(index) != strs[0].charAt(index))
18 return res.toString();
19 }
20 res.append(strs[0].charAt(index));
21 index++;
22 }
23 return res.toString();
24 }
2 int min = Integer.MAX_VALUE;
3 for(int i=0; i<strs.length;i++)
4 min = Math.min(min,strs[i].length());
5 return min;
6 }
7
8 public String longestCommonPrefix(String[] strs) {
9 if (strs == null || strs.length == 0)
10 return "";
11
12 StringBuilder res = new StringBuilder();
13 int index = 0;
14 int len = minlen(strs);
15 while (index < len){
16 for (int i=1; i<strs.length;i++){
17 if (strs[i].charAt(index) != strs[0].charAt(index))
18 return res.toString();
19 }
20 res.append(strs[0].charAt(index));
21 index++;
22 }
23 return res.toString();
24 }
Reference:http://blog.csdn.net/linhuanmars/article/details/21145733
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。