力扣经典算法篇-16-最长公共前缀（顺序查找法，二分查找法，分治算法）

1、题干

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

示例 1：
输入：strs = [“flower”,“flow”,“flight”]
输出：“fl”

示例 2：
输入：strs = [“dog”,“racecar”,“car”]
输出：“”
解释：输入不存在公共前缀。

提示：
1 <= strs.length <= 200
0 <= strs[i].length <= 200
strs[i] 如果非空，则仅由小写英文字母组成

2、解题

方法一：按列顺序比较

取第一个元素作为基准字符串，从左到右依次取出1,2，3…n个元素组成前缀字符串，与之后的所有字符串都进行比较。如果之后的字符串都满足该前缀条件，则基准字符串继续向后添加元素；如果不满足，则当前前缀字符串去除最后一个元素，则为所有字符串的最大公共前缀。
这种方法，最容易想到，代码简单且但时间复杂度为O（n^2）,相对效率低了一点。
代码示例：

public static String longestCommonPrefix(String[] strs) {
        StringBuilder builder = new StringBuilder();
        String firstStr = strs[0];
        for (int i = 0; i < strs[0].length(); i++) {
            builder.append(firstStr.charAt(i));
            for (int j = 1; j < strs.length; j++) {
                if (!strs[j].startsWith(builder.toString())) {
                    return builder.substring(0, builder.length() - 1);
                }
            }
        }
        return builder.toString();
    }

以上是基于java已有的startsWith方法进行处理，在C中不够通用，字符处理代码示例如下：

public static String longestCommonPrefix(String[] strs) {
        StringBuilder builder = new StringBuilder();
        String firstStr = strs[0];
        for (int i = 0; i < strs[0].length(); i++) {
            char c = firstStr.charAt(i);
            boolean flag = true;
            for (int j = 1; j < strs.length; j++) {
                if (strs[j].length()>i){
                    char c1 = strs[j].charAt(i);
                    if (c1 != c){
                        flag = false;
                        break;
                    }
                } else {
                    flag = false;
                }
            }
            if (flag){
                builder.append(c);
            } else {
                break;
            }
        }
        return builder.toString();
    }

方法二：二分查找法

上诉的按列展开法，时间复杂度O（n^2）,因为从1到最后每一种可能都需要比较，比较次数较多，效率相对较低。
二分查找法是一种优化顺序查找的常见算法。通过二分的方式，减少了整体比较的次数。

代码示例：

public static String longestCommonPrefix(String[] strs) {
    if (strs == null || strs.length == 0) {
        return "";
    }
    int minLength = Integer.MAX_VALUE;
    for (String str : strs) {
        minLength = Math.min(minLength, str.length());
    }
    int low = 0, high = minLength;
    while (low < high) {
        int mid = (high - low + 1) / 2 + low;      // 取中间值
        if (isCommonPrefix(strs, mid)) {      // 比较中间值
            low = mid;                       // 中间值能满足公共前缀，取后半部分，在次二分
        } else {
            high = mid - 1;                // 中间值能不满足公共前缀，取前半部分，在次二分
        }
    }
    return strs[0].substring(0, low);
}
public static boolean isCommonPrefix(String[] strs, int length) {
    String str0 = strs[0].substring(0, length);
    int count = strs.length;
    for (int i = 1; i < count; i++) {
        String str = strs[i];
        for (int j = 0; j < length; j++) {
            if (str0.charAt(j) != str.charAt(j)) {
                return false;
            }
        }
    }
    return true;
}

方法三：分治法

分治法是一种常见的算法策略。将大的问题逐步分解成多组小问题，得到最终的结果。
思路：将整个数组，最终拆分成每一个字符串。然后每一对2个相邻的字符串取出最大公共前缀。在取相邻的4个计算公共前缀（此时只需要比较1和2字符串的公共前缀串g1和3和4字符串的公共前缀串g2即可，减少了比较次数）。在依次取8个元素（只比较2个公共的前缀串），直到最终全部合并比较完成。
相对来说，这个分治算法是有些难度的，但套路比较深，多见识一下学习该种解题的套路。

代码示例：

public static String longestCommonPrefix(String[] strs) {
        if (strs == null || strs.length == 0) {
            return "";
        } else {
            return longestCommonPrefix(strs, 0, strs.length - 1);
        }
    }
    public static String longestCommonPrefix(String[] strs, int start, int end) {
        if (start == end) {
            return strs[start];
        } else {
            int mid = (end - start) / 2 + start;
            String lcpLeft = longestCommonPrefix(strs, start, mid);
            String lcpRight = longestCommonPrefix(strs, mid + 1, end);
            return commonPrefix(lcpLeft, lcpRight);
        }
    }
    public static String commonPrefix(String lcpLeft, String lcpRight) {
        int minLength = Math.min(lcpLeft.length(), lcpRight.length());
        for (int i = 0; i < minLength; i++) {
            if (lcpLeft.charAt(i) != lcpRight.charAt(i)) {
                return lcpLeft.substring(0, i);
            }
        }
        return lcpLeft.substring(0, minLength);
    }

向阳出发，Dare To Be！！！