1. 输入: ["flower","flow","flight"]
  2. 输出: "fl"

思路1：横向比较

LCP(s1,s2,..sn) = LCP(LCP(LCP(s1,s2),s3)….sn);
将每个字符一一比较得到当前最长前缀，如果当前最长前缀为空，则循环停止，时间复杂度O（mn）,空间复杂度O（1）；
外循环是数组{
内循环是比较
}

思路2：纵向比较

外循环是比较{
内循环是数组
}

思路3：分治算法

分治模版：
masterfun(数组){
return masterfun(数组，0，数组长度-1)；
}
masterfun（数组，start，end）{
if(start ==end )return 数组[start];
else{
int mid =(end -start)/2+start;
左分支：masterfun(数组，0，mid);
有分支：masterfun(数组，mid+1,end);
合并： subfun(左分支，右分支)；
}
}
subfun(左分支，右分支)

  1. class Solution {
  2.     //横向扫描
  3.     // public String longestCommonPrefix(String[] strs) {
  4.     //     if(strs.length==0) return "" ;
  5.     //     if(strs.length==1) return strs[0];
  6.     //     String prefix = strs[0];
  7.     //     for(int i=1;i<strs.length;i++){
  8.     //         String temp ="";
  9.     //         for(int j=0;j<prefix.length()&& j<strs[i].length();j++){
  10.     //             if(strs[i].charAt(j)==prefix.charAt(j)){
  11.     //                 temp+=strs[i].charAt(j);
  12.     //             }else{
  13.     //                 break;
  14.     //             }
  15.     //         }
  16.     //         prefix = temp;
  17.     //     }
  18.     //     return prefix;
  19.     // }
  20.     //纵向扫描
  21.     // public String longestCommonPrefix(String[] strs) {
  22.     //     if(strs==null||strs.length==0) return "";
  23.     //     String prefix = strs[0];
  24.     //     for(int i=0;i<prefix.length();i++){
  25.     //         for(int j=1;j<strs.length;j++){
  26.     //             if(i==strs[j].length() || prefix.charAt(i)!= strs[j].charAt(i)){
  27.     //                 return prefix.substring(0,i);
  28.     //             }
  29.     //         }  
  30.     //     }
  31.     //     return prefix;
  32.     // }
  33.     //分治算法
  34.     public String longestCommonPrefix(String[] strs) {
  35.         if(strs==null || strs.length ==0) return "";
  36.         return longestCommonPrefix(strs,0,strs.length-1);
  37.     }
  38.     private String longestCommonPrefix(String[] strs,int start,int end){
  39.         if(start==end) return strs[start];
  40.         else{
  41.             int mid = (end-start)/2+start;
  42.             String leftPre = longestCommonPrefix(strs,start,mid);
  43.             String rightPre = longestCommonPrefix(strs,mid+1,end);
  44.             return commonPre(leftPre,rightPre);
  45.         }
  46.     }
  47.     private String commonPre(String left,String right){
  48.         int len = Math.min(left.length(),right.length());
  49.         int count =0;
  50.         for(int i=0;i<len;i++){
  51.             if(left.charAt(i)!=right.charAt(i)){
  52.                return left.substring(0,i);
  53.             }
  54.         }
  55.         return left.substring(0,len);
  56.     }
  60. }