14.md

14. Longest Common Prefix

Write a function to find the longest common prefix string amongst an array of strings.

####Analysis & Solution Use divide and conquer algorithm to solve this problem. T(n) = 2T(n/2) + O(n)

private static String EMPTY_STRING = "";
    public String longestCommonPrefix(String[] strs) {
        if(strs == null || strs.length == 0){
            return EMPTY_STRING;
        }
        return getLCP(strs, 0, strs.length - 1);
    }
    private String getLCP(String[] strs, int left, int right){
        if(left > right){
            return EMPTY_STRING;
        }
        if(left == right){
            return strs[left];
        }
        //divide
        int middle = (left + right)/2;
        
        String leftRes = getLCP(strs, left, middle);
        String rightRes = getLCP(strs, middle+1, right);
        
        //conquer
        String max = EMPTY_STRING;
        for(int i = 0; i < leftRes.length() && i < rightRes.length(); i++){
            String leftTemp = leftRes.substring(0, i+1);
            String rightTemp = rightRes.substring(0,i+1);
            if(leftTemp.equals(rightTemp)){
                 max = leftTemp.length() >= max.length() ? leftTemp : max; 
                 continue;
            }
            break;
        }
        return max;
    }