力扣14：最长公共前缀

方法一：水平扫描法

class Solution {
    public String longestCommonPrefix(String[] strs) {
    if (strs.length == 0) return "";
    String prefix = strs[0];
    for (int i = 1; i < strs.length; i++)
        while (strs[i].indexOf(prefix) != 0) {
            prefix = prefix.substring(0, prefix.length() - 1);
            if (prefix.isEmpty()) return "";
        }        
    return prefix;
}
}

公共前缀一定是第一个子串的前缀，首先把整个第一个子串当作前缀，然后向下查询，如果发现全部以第一个子串开头，则第一个子串就是前缀；如果出现不同情况，prefix从后往前缩短即可。

这里很巧妙，先找出第二个子串和第一个子串的公共前缀，然后再找第三个和前两个的公共前缀。以此类推

方法二：水平扫描

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];
}

这是最容易想到的方法。以第一个子串的每一个字符进行判断。后续的列如果出现和第一个串字符不一样，或者出现没第一个子串长。那就只能截取到第i个位置之前。相当于在水平扫描列

方法三：分治法

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);
}

分享一下官网给出的图片。加深对分治算法的学习。