图解LeetCode14：最长公共前缀（递归，二分查找）

LeetCode14：最长公共前缀

编写一个函数来查找字符串数组中的最长公共前缀。

如果不存在公共前缀，返回空字符串""。

示例：

输入：strs = ["flowers", "flow", "flight"]
输出："fl"

输入：strs = ["dog", "racecar", "car"]
输出：""
解释：不存在公共前缀

思路1：

递归法

我们可以采用各个字符进行比较，比如：将待比较的最大公共前缀为strs[0]，就是flowers，然后与strs[1]相比，flowers和flow的公共前缀为flow，则更新公共前缀为flow，再与flight相比，公共前缀为f，则返回f。

如果再第一次比较，比如dog和racecar相比没有公共前缀，则直接返回""，不用再往下遍历

解法1：

public String longestCommonPrefix(String[] strs){
    // 如果传入参数strs为空，返回""
    if(strs == null || strs.length == 0) return "";

    // 将第一个元素作为初始公共字串
    String commonPrefix = strs[0];
    // 遍历strs，比较公共字串
    for (int i = 1; i < strs.length; i++) {
        int j = 0;
        // 遍历第i个元素字符串
        while(j < strs[i].length() && j < commonPrefix.length() ){

            if (strs[i].charAt(j) != commonPrefix.charAt(j)) commonPrefix = strs[i].substring(0,j);
            j ++;
        }
    }
    return commonPrefix;
}

思路2：

二分法

可以按照二分法，逐渐的将公共前缀分割，判断是否所有的元素都是以该前缀开头，如果不是，将公共前缀往前继续二分分割，如果是，将公共前缀往后继续二分分割，直到满足最长的公共前缀要求

其实在二分查找最长公共前缀的时候，应该选择最短的那个作为初始公共前缀，因为公共前缀的数值不可能超过最短的那个，所以就是以flow作为初始公共前缀进行二分查找

解法2：

public String longestCommonPrefix2(String[] strs){
    // 如果传入参数strs为空，返回""
    if(strs == null || strs.length == 0) return "";
    // 找到最短的字符串
    String prefix = "";
    int minLen = strs[0].length();
    for (String str : strs) {
        if (str.length() <= minLen){
            minLen = str.length();
            prefix = str;
        }
        minLen = Math.min(minLen, str.length());
    }
    // 作为二分查找的索引，当左边大于了右边，证明二分查找结束
    int low = 0, high = minLen;
    // 是否strs全部匹配
    boolean isCommon = true;
    // 结果
    String res = "";
    while(low < high){
        // 找到二分值
        int mid = (high - low + 1) / 2 + low;
        res = prefix.substring(0, mid);
        isCommon = true;
        // 遍历所有数值
        for (String str : strs) {
            // 元素是否全部以前缀开头
            if (!str.startsWith(res)) {
                isCommon = false;
                high = mid - 1;
                break;
            }
        }
        if (isCommon) low = mid;
    }
    // 退出循环再次最后一次更新mid
    int mid = (high - low + 1) / 2 + low;
    res = prefix.substring(0, mid);
    return res;
}

测试

public static void main(String[] args) {
LeetCode14 lc = new LeetCode14();
        System.out.println(lc.longestCommonPrefix(new String[]{"flowers", "flow", "flight"}));
        System.out.println(lc.longestCommonPrefix2(new String[]{"flowers", "flowww", "flowight"}));
    }

结果

fl
flow