一、问题描述
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 "".
意思是给你一个字符串数组，求数组中最长的公共前缀字符串。如果没有最长公共前缀字符串，则返回零。没有最长公共前缀的情况有两种：一种是第一个字符就存在不相等的情况，还有一种是空数组！很容易会把空数组的情况遗漏掉，我就是。。。。是我考虑不够周全。
二、生词
optimize vi. /'ɒptɪmaɪz/ 优化
三、样例及说明
四、解题思路及代码
1、首先判断字符数组的长度，如果等于0就返回空字符串（问题描述中的两种情况之空数组）；
2、遍历数组，求出最短字符串的长度；
3、创建一个StringBuffer对象用来保存公共前缀，以及一个栈；
4、遍历寻找数组中的公共前缀。
1 class Solution {
2 public String longestCommonPrefix(String[] strs) {
3 if(strs.length==0) return "";
4 int minLen = 9999;
5 for(String s : strs) {
6 minLen = Math.min(minLen, s.length());
7 }
8 StringBuffer sb = new StringBuffer("");
9 Stack<Character> st = new Stack<>();
10 for(int i=0; i < minLen; i++) {
11 st.push(strs[0].charAt(i));//以第一个数组作为比较基准
12 for(int j=1; j < strs.length; j++) {
13 if(strs[j].charAt(i)!=st.peek()) {//只要有一个字符不相等就直接返回sb中的内容
14 return sb.toString();
15 }
16 }
17 sb.append(st.pop());
18 }
19 return sb.toString();
20 }
21 }
我的方法虽然可以做出题来，但是根据数据显示，我只打败了59%的Java提交者，显然代码需要优化的地方有很多，且往下看。。。
在看了别人解题的代码后，我的代码有以下缺漏：
1、如果数组中只要一个元素，那么我的代码就会重复push()、pop()这两个无效操作，所以一开始就要判断如果数组长度为1，直接返回数组元素。
2、没有内容的StringBuffer对象调用toString()方法不会发生空指针异常。。。是什么让我产生会发生异常的想法。。。。
3、代码没有利用字符串的一些方法解题，因为大神的代码只用了字符串的方法就解出来了，我还那么麻烦用了栈。。。
其实利用startsWith()方法或者indexOf()方法就可以解题，关键思想是把数组的第一个元素假设是前缀prefix，在迭代的时候更新prefix。怎么更新法呢？就是如果后一个字符串不是以prefix为前缀（或者后一个字串中不包含prefix、包含prefix但下标返回不是0），就把prefix截取从0-length()-1的字串赋给prefix，如此迭代下去，最终的结果就是最长公共前缀。
1 class Solution { //改进
2 public String longestCommonPrefix(String[] strs) {
3 if(strs==null || strs.length==0) return "";
4 if(strs.length==1) return strs[0];
5 String prefix = strs[0];
6 for(int i=1; i<strs.length; i++) {
7 while(!strs[i].startsWith(prefix)) {
8 prefix = prefix.substring(0,prefix.length()-1);
9 }
10 if(prefix.length()==0) break;
11 }
12 return prefix;
13 }
14 }
从Runtime就可以看出优化了不少，代码比我最初的思路也更易懂，是我把问题复杂化了。。。
然后同一个思路写的代码，因为没有在prefix.length()==0的时候break，运行出来的时间差了1ms。。。所以多余的步骤能避免就要避免啊
在Solution上一共有四种解题方法：
1、Horizontal scanning（水平扫描法）：就是上面我改进版的代码思路，从头开始先两两找到最长公共前缀再继续与后一个元素找。
2、Vertical scanning（垂直扫描法）
1 public String longestCommonPrefix(String[] strs) {
2 if (strs == null || strs.length == 0) return "";
3 for (int i = 0; i < strs[0].length() ; i++){
4 char c = strs[0].charAt(i);
5 for (int j = 1; j < strs.length; j ++) {
6 if (i == strs[j].length() || strs[j].charAt(i) != c)
7 return strs[0].substring(0, i);
8 }
9 }
10 return strs[0];
11 }
3、Divide and conquer（分治法）
1 public String longestCommonPrefix(String[] strs) {
2 if (strs == null || strs.length == 0) return "";
3 return longestCommonPrefix(strs, 0 , strs.length - 1);
4 }
5
6 private String longestCommonPrefix(String[] strs, int l, int r) {
7 if (l == r) {
8 return strs[l];
9 }
10 else {
11 int mid = (l + r)/2;
12 String lcpLeft = longestCommonPrefix(strs, l , mid);
13 String lcpRight = longestCommonPrefix(strs, mid + 1,r);
14 return commonPrefix(lcpLeft, lcpRight);
15 }
16 }
17
18 String commonPrefix(String left,String right) {
19 int min = Math.min(left.length(), right.length());
20 for (int i = 0; i < min; i++) {
21 if ( left.charAt(i) != right.charAt(i) )
22 return left.substring(0, i);
23 }
24 return left.substring(0, min);
25 }
四、Binary search（二分查找法）
1 public String longestCommonPrefix(String[] strs) {
2 if (strs == null || strs.length == 0)
3 return "";
4 int minLen = Integer.MAX_VALUE;
5 for (String str : strs)
6 minLen = Math.min(minLen, str.length());
7 int low = 1;
8 int high = minLen;
9 while (low <= high) {
10 int middle = (low + high) / 2;
11 if (isCommonPrefix(strs, middle))
12 low = middle + 1;
13 else
14 high = middle - 1;
15 }
16 return strs[0].substring(0, (low + high) / 2);
17 }
18
19 private boolean isCommonPrefix(String[] strs, int len){
20 String str1 = strs[0].substring(0,len);
21 for (int i = 1; i < strs.length; i++)
22 if (!strs[i].startsWith(str1))
23 return false;
24 return true;
25 }
五、反思总结
String的substring(0,0)方法返回空字符串。