算法：最长公共前缀

本文首发自 RiverLi的公众号，欢迎关注，期待与您更进一步交流。

题目描述

题目来源： https://leetcode-cn.com

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

示例 1:

输入: ["flower","flow","flight"]
输出: "fl"

示例 2:

输入: ["dog","racecar","car"]
输出: ""

解法

解法一

这种解法是暴力循环法，从题目可知：最长公共前缀的最长长度一定是字符串数组中长度最短哪个字符串。

1. 首先找出长度最短的字符串str，加入str="abcf"。
2. 依次对'abcf'、'abc'、'ab'、'a'进行筛选，判断哪个是所有其他字符串的前缀。

具体代码如下：

public String longestCommonPrefix(String[] strs) {
    if(strs.length==0){
        return "";
    }
    String minLengthString = strs[0];
    int minlength = minLengthString.length();
    for(int i=1; i<strs.length; i++) {
        if(minlength>strs[i].length()){
            minLengthString = strs[i];
            minlength = strs[i].length();
        }
    }

    int index = minlength;
    String result = "";
    while(index>0){
        String subString = minLengthString.substring(0, index);
        boolean isMax = true;
        for(int i=1; i<strs.length; i++){
            if(strs[i].startsWith(subString) == false){
                isMax = false;
                break;
            }
        }
        if(isMax){
            result = subString;
            break;
        }
        index --;
    }
    return result;
}

解法二

这种方法称之为水平扫描法，用一张图来表示其具体过程如下：

图解

首先假设最长前缀result=str[0], 遍历字符串数组，依次与result做比较，找出其最长前缀，然后更新result，再进行下一次比较。

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

解法三

这种解法与前面的解法不同的是，它是比较的字符。看下图:

图解

对str[0]按字符遍历，与其他字符串依次比较对应位置上的字符，并记录查找位置，如果找到不相等或者对应字符串的长度到了限制，就找到了。

代码如下：

public String longestCommonPrefix4(String[] strs) {
    if(strs.length == 0) {
        return "";
    }
    for(int i=0; i<strs[0].length(); i++) {
        char c = (char) strs[0].charAt(i);
        for(int j=1; j<strs.length; j++) {
            if( c!=strs[j].charAt(i) || i==strs[j].length() ) {
                return strs[0].substring(0, i);
            }
        }
    }

    return strs[0];
}

解法四

利用分治的思想。

//分治
public String longestCommonPrefix5(String[] strs) {
    if(strs.length == 0) {
        return "";
    }
    int length = strs.length;
    return this.commonPrefix(strs, 0, length-1);
}

public String commonPrefix(String[] strs, int left, int right) {
    if(left == right) {
        return strs[left];
    } 
    int mid = (left + right) / 2;
    String leftStr = commonPrefix(strs, left, mid);
    String rightStr = commonPrefix(strs, mid+1, right);
    return this.commonPrefix(leftStr, rightStr);
}
public String commonPrefix(String left, String right) {
    int minLength = Math.min(left.length(), right.length());
    for (int i=0; i<minLength; i++) {
        if( left.charAt(i)!=right.charAt(i) ) {
            return left.substring(0, i);
        }
    }
    return left.substring(0, minLength);
}

解法五

利用二分法的思想

1. 找出最短的字符串记为m;
2. 对字符串m进行二分,分割点记为mid，用tmp表示m[low...high]。
3. 如果tmp为所有字符串的前缀，则mid右移，否则左移，直到low>high。
   代码如下：

public String longestCommontPrefix6(String[] strs) {
    if(strs.length == 0) {
        return "";
    }
    int min = Integer.MAX_VALUE;
    for(String str : strs) {
        min = Math.min(min, str.length());
    }
    int low = 1;
    int high = min;
    while(low <= high) {
        int middle = (low + high)/2;
        if(this.isCommontPrefix(strs, middle)) {
            low = middle + 1;
        } else {
            high = middle - 1;
        }
    }
    return strs[0].substring(0, (low + high)/2);
}

public boolean isCommontPrefix(String[] strs, int length) {
    String tmp = strs[0].substring(0, length);
    for (int i=0; i<strs.length; i++) {
        if(!strs[i].startsWith(tmp)) {
            return false;
        }
    }
    return true;
}

总结

这个问题有多种思路和解决办法，个人觉得解法三比较新颖，让人想不到。其实还有一种想法就是构造树，这个代码就比较复杂了，有兴趣的可以自己写写看。