最长公共前缀

来源Leetcode第14题最长公共前缀

编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀，返回空字符串 “”。

示例 1:

输入: [“flower”,”flow”,”flight”]
输出: “fl”

列遍历

先进行列扫描，如果当前列的字符都相等，则进行下一列字符的扫描，直到扫描到不相等的字符。
代码如下:

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

行遍历

当然也可以横向扫描，找到第一字符串与第二字符串之间的最长公共前缀，记为LCP(1,2)，之后再比较LCP(1,2)与第三个字符串之间的最长公共前缀，以此类推，由于没学Java，代码看的不是很懂。

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

递归

注意到LCP(S1~Sn) = LCP(LCP(LCP(S1~Sk),LCP(Sk+1~Sn)),因而我们可以将原问题LCP(Si~Sj)分解成LCP(Si~Smid)与LCP(Smid+~Sj),其中mid=i+j/2,用子问题的解构造原问题的解。
代码如下：

public String longestCommonPrefix(String[] strs) {
    if (strs == null || strs.length == 0) return "";    
        return longestCommonPrefix(strs, 0 , strs.length - 1);//初始化,将原问题分解为2个小问题,分别求LCPleft与LCPright
}

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); //求左右两个LCP
   }
}

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