思路一：

1. 水平扫描法。取出输入的第一个字符串tt，依次将tt的第i个字母与后面所有的 第1---n个字符串的第i个字母进行比较。如果字母相同，j++比较后一个字符串（注意！最短的字符串的长度限制）；一旦有不同，返回子串0---i-1。

class Solution {
    public String longestCommonPrefix(String[] strs) {
        int n=strs.length;
        if(n==0){
            return "";
        }
    String tt = strs[0];
    int i = 0;
    for (i = 0; i < tt.length(); i++) {
      int j = 1;
      char ch = tt.charAt(i);
      while (j < n) {
        String sj = strs[j];
        if (i < sj.length() && ch == sj.charAt(i)) {
          j++;
        }else {
          return tt.substring(0, i) ;
        }
      }
    }
    return tt.substring(0, i) ;
  } 
}

查看官方解答后补充思路
思路二：

1. 分治。套路分治的代码模板吧。
   主要有三个函数，第一个函数LCP，作用是'包装'，和排除空的情况，因为空list会下标超限。
   第二个函数fenzhi就是divide步骤，首先写好递归终止条件，进行左半边、右半边的递归，递归得到两部分的最长前缀后进行合并。调用Conquer函数。
   第三个函数是Conquer。根据左边、右边的最长前缀，得到整体的最长前缀。
   分治结束。
2. 重要的是，最长公共前缀具有子问题优化的特点，整体的最长前缀是前后两部分最长前缀的前缀，因此应用分治。

image.png

public class longestCPfenzhi {
  /*分治的思想*/
  
  public static String LCP(List<String> list,int start,int end) {
    if(list.isEmpty()) {
      return "";
    }
    return fenzhi(list,start,end);
  }

  public static String fenzhi(List<String> list,int start,int end) {//divide步骤
    if(start==end) {
      return list.get(start);
    }
    int mid=(start+end)/2;
    String sleft=fenzhi(list,start,mid);
    String sright=fenzhi(list,mid+1,end);
    return Conquer(sleft,sright);
  }
  
  public static String Conquer(String sleft,String sright) {
    int minlen=Math.min(sleft.length(), sright.length());
    for(int i=0;i<minlen;i++) {
      if(sleft.charAt(i)!=sright.charAt(i)) {
        return sleft.substring(0, i);
      }
    }
    return sleft.substring(0, minlen);
  }
  
  public static void main(String[] args) {
    // TODO Auto-generated method stub
    Scanner sc = new Scanner(System.in);
    String str = sc.nextLine();
    sc.close();
    Pattern p = Pattern.compile("\"(.*?)\"");
    Matcher m = p.matcher(str);
    List<String> list = new ArrayList<String>();
    while (m.find()) {
      list.add(m.group().replaceAll("\"", ""));
    }
    String s=LCP(list,0,list.size()-1);
    System.out.println(s);
  }
}

思路三：

1. 二分的思想。套路二分模板吧。
   在选取前缀时直接找到最短的字符串，切半，如果前一半是所有字符串的公共前缀（用isCommonPrefix函数判断）那么移动low指针；如果不是，移动high指针。
   前缀占字符串：1/2，3/4（isCommonPrefix），7/8.....
   1/4（! isCommonPrefix）......

public class LCPerfen {
  
  public static boolean isCommonPrefix(List<String> list,String prefix) {
    for(int i=0;i<list.size();i++) {
      if(!list.get(i).startsWith(prefix)) {
        return false;
      }
    }
    return true;
  }
  
  public static String Erfen(List<String> list) {
    int minlen=Integer.MAX_VALUE;
    for(int i=0;i<list.size();i++) {
      minlen=Math.min(minlen, list.get(i).length());
    }
    int low=1;//必须是1
    int high=minlen;//必须是这个长度
    while(low<high){
      int middle=(low+high)/2;
      String prefix=list.get(0).substring(0,middle);
      if(isCommonPrefix(list,prefix)) {
        low=middle+1;
      }else {
        high=middle-1;
      }
    }
    return list.get(0).substring(0,(low+high)/2);
  }

  public static void main(String[] args) {
    // TODO Auto-generated method stub
    Scanner sc = new Scanner(System.in);
    String str = sc.nextLine();
    sc.close();
    Pattern p = Pattern.compile("\"(.*?)\"");
    Matcher m = p.matcher(str);
    List<String> list = new ArrayList<String>();
    while (m.find()) {
      list.add(m.group().replaceAll("\"", ""));
    }
    String s=Erfen(list);
    System.out.println(s);
  }
}