Longest Common Prefix

问题描述

Write a function to find the longest common prefix string amongst an array of strings.

算法

代码一

 1 public String longestCommonPrefix(String [] strs){
 2         if(strs.length==0)
 3             return null;
 4         String s=null;
 5         int prefixLength=0;
 6         boolean b=false;
 7         int minLength=strs[0].length();
 8         for(int i=1;i<strs.length;i++){
 9             if(strs[i].length()<minLength){
10                 minLength=strs[i].length();
11             }
12         }
13         for(;prefixLength<minLength;prefixLength++){
14             for(int j=0;j<strs.length;j++){
15                 if(strs[j].charAt(prefixLength)!=strs[0].charAt(prefixLength)){    
16                     b=true;
17                     break;
18                 }
19             }
20             if(b)
21                 break;
22         }
23         if(prefixLength==0)
24             return null;
25         s=strs[0].substring(0, prefixLength);
26         return s;
27     }

代码二

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

注意事项

1.如果String s=null,则s.length非法

2."hamburger".substring(4, 8) returns "urge" 而不是"urger",同时"hamburger".substring(4, 8) returns "" 而不是null

3.break只能跳出一层循环，如果你的循环是嵌套循环，那么你需要按照你嵌套的层次，逐步使用break来跳出.

4.不要混了indexOf和charAt。这是 indexOf：if the string argument occurs as a substring within this object, then the index of the first character of the first such substring is returned; if it does not occur as a substring, -1 is returned.例子："aersdfgh".indexOf("aer")=0。

5.这道题目中，没有共同前缀返回""而不是返回null。null和""的区别请见http://www.cnblogs.com/hongten/archive/2012/11/08/java_null.html。