Leetcode14-最长公共前缀

虽然只是一道简单题，但是看了官方的题解还是有所收获，在此记录一下。

自己写的解法：

public  String longestCommonPrefix(String[] strs) {
        if (strs == null || strs.length == 0) return "";
        String result = strs[0];
        for (String str : strs) {
            if (str.length() == 0) return "";
            for (int i = 0; i < Math.min(str.length(), result.length()); i++) {
                if (i == str.length() - 1 && str.charAt(i) == result.charAt(i)) {
                    result = result.substring(0, i + 1);
                    break;
                }
                if (str.charAt(i) != result.charAt(i)) {
                    result = result.substring(0, i);
                    break;
                }
            }
        }
        return result;
    }

看官方解法的收获

一、String.indexof(String s)的使用

虽然我的解题思路和官方的解题思路1一致，但是在代码简洁性上来讲还是有所不如，下面是官方解法：

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

这段代码的精妙之处就在于使用了indexOf来判断当前最大前缀的结果在最新的字符串str中的匹配结果,如果存在，就会返回prefix的首个字符在最新字符串str所对应的下标，如果没有匹配就会返回-1。例如：

String a1 = "ha";
System.out.println(a1.indexOf("hah")); //输出结果为-1
String a2 = "hahahaheiheihei";
System.out.println(a2.indexOf("hah"));//输出结果为0
String a3 = "hahahaheiheihei";
System.out.println(a3.indexOf("hahei"));//输出结果为4

就拿a3的例子来说，如果结果不是0，那么就会执行substring，去掉最后一个字母，再进行匹配，直到找出对应结果为0的字符串，这时如果没有公共前缀的话，prefix就会变为空字符串，后面就没必要进行判断了，可以加一个判断，直接返回。

二、分治的使用

思想较为简单，代码也比较固定，总的来说就是分别两两比较字符串再进行合并比较，(这里的比较的意思就是找出公共最长前缀并返回，作为新的比较字符串)直接贴代码：

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