今天做的是LeetCode習題10，尋找最長的前綴。用的是最一般的方法，很好理解，但是方法比較笨。

具體思路就是先獲取字符串數組中每一個字符串的長度，找到最小值。用一個嵌套循環，找到相同的前綴，完成任務。

代碼如下：

	public String longestCommonPRefix(String[] strs) {		if(strs.length==0)			return null;		String result="";		int lengthOfStrs=java.lang.Integer.MAX_VALUE;		for(int i=0;i<strs.length;i++){			if(strs[i].length()<lengthOfStrs)				lengthOfStrs=strs[i].length();		}		for(int j=0;j<lengthOfStrs;j++){			for(int i=0;i<strs.length-1;i++){				if(strs[i].charAt(j)!=strs[i+1].charAt(j))					return result;			}			result+=strs[0].charAt(j);		}		return result;            }重點是for循環。注意最外層的循環是按列增加的。比較的是當前字符串的第j個位置和后一個字符串的第j個位置。如果一旦發現不同則直接返回之前的字符串，否則講這個字符加到結果中。
參看官網上有4種很棒的方法：
1.Horizontal Scanning
采用的思想就是先跳出第一個和第二個的共同前綴，再挑出此前綴和第三個的共同前綴，以此類推。
官方給的代碼也很值得學習。
public String longestCommonPrefix(String[] strs) {	    if (strs.length == 0) return "";	    String prefix = strs[0];int a=0;	    for (int i = 1; i < strs.length; i++)	        while ((a=strs[i].indexOf(prefix) )!= 0) {	            prefix = prefix.substring(0, prefix.length() - 1);	            if (prefix.isEmpty()) return "";	        }        	    return prefix;	}2.Vertical Scanning
第二種方法和我采取的思路是一樣的，但是代碼要比我寫的好的多。
public String longestCommonPrefix(String[] strs) {    if (strs == null || strs.length == 0) return "";    for (int i = 0; i < strs[0].length() ; i++){        char c = strs[0].charAt(i);        for (int j = 1; j < strs.length; j ++) {            if (i == strs[j].length() || strs[j].charAt(i) != c)                return strs[0].substring(0, i);                     }    }    return strs[0];}首先，并不提前計算最短的字符串長度。一開始我計算的原因是防止發生數組越界的問題，但這個方法直接使用了第一個字符串的長度，在判斷條件中加了是否當前指數等于字符串長度的判斷，避免了越界問題，加快了運行速度。
直接以第一個字符串為依托，與其余的字符串進行比較，如果第j個字符串的第i個位置的字符不相同或者是超過長度時則直接返回第一個字符串之前的部分。不用再用另外一個變量存儲結果了。
所謂vertical指的就是依次比較所以字符串中的第j列。
substring(int begin,int length):測試過，第二個變量是長度，所以在調用substring時返回的正好是第0到第i-1位字符。
3.Divide and Conquer
第三種方法采用的是分治策略。先將全部字符串不斷向下一份為二，直到每組中只有一個或者兩個的時候算出這兩個的公共前綴，之后再依次合并兩組之間的公共前綴，解決問題。
這種方法在較好情況下可以降低時間復雜度。
代碼如下：
public String longestCommonPrefix(String[] strs) {    if (strs == null || strs.length == 0) return "";            return longestCommonPrefix(strs, 0 , strs.length - 1);}private String longestCommonPrefix(String[] strs, int l, int r) {    if (l == r) {        return strs[l];    }    else {        int mid = (l + r)/2;        String lcpLeft =   longestCommonPrefix(strs, l , mid);        String lcpRight =  longestCommonPrefix(strs, mid + 1,r);        return commonPrefix(lcpLeft, lcpRight);   }}String commonPrefix(String left,String right) {    int min = Math.min(left.length(), right.length());           for (int i = 0; i < min; i++) {        if ( left.charAt(i) != right.charAt(i) )            return left.substring(0, i);    }    return left.substring(0, min);}看著比較多，其實邏輯還是很簡單的。尤其在找出相同前綴的時候，因為是找兩個結果前綴的，所以直接依次向下比較第i個位置的字符就可以了。
4.Binary Search
這種方法較第二種方法進行了改進，第二種方法是直接從第一個位置開始向后搜索的，這種方法是從中間位置開始，如果到中間位置存在公共前綴是成立的，則搜索長度++，否則--，直到low<high。
代碼如下：
public String longestCommonPrefix(String[] strs) {    if (strs == null || strs.length == 0)        return "";    int minLen = Integer.MAX_VALUE;    for (String str : strs)        minLen = Math.min(minLen, str.length());    int low = 1;    int high = minLen;    while (low <= high) {        int middle = (low + high) / 2;        if (isCommonPrefix(strs, middle))            low = middle + 1;        else            high = middle - 1;    }    return strs[0].substring(0, (low + high) / 2);}private boolean isCommonPrefix(String[] strs, int len){    String str1 = strs[0].substring(0,len);    for (int i = 1; i < strs.length; i++)        if (!strs[i].startsWith(str1))            return false;    return true;}這個方法把時間復雜度降低到了log級別。