题解 | #最长公共前缀#

分治法

 public String longestCommonPrefix (String[] strs) {
        // write code here

        if (strs == null || strs.length == 0){
            return "";
        }

        return longestCommonPrefix(strs,0,strs.length-1);
    }

    private String longestCommonPrefix (String[] strs,int start,int end) {
        // write code here

        if (start == end){
            return strs[start];
        }else {
            int mid = (start + end) / 2;
            String leftCommonPrefix = longestCommonPrefix(strs,start,mid);
            String rightCommonPrefix = longestCommonPrefix(strs,mid + 1,end);

            return CommonPrefix(leftCommonPrefix,rightCommonPrefix);
        }
    }

    private String CommonPrefix(String leftCommonPrefix, String rightCommonPrefix) {

        int minlen = Math.min(leftCommonPrefix.length(),rightCommonPrefix.length());

        for (int i = 0; i < minlen; i++) {

            if (leftCommonPrefix.charAt(i) != rightCommonPrefix.charAt(i)){
                return leftCommonPrefix.substring(0,i);
            }
        }

        return leftCommonPrefix.substring(0,minlen);
    }