14. Longest Common Prefix

题目：

Write a function to find the longest common prefix string amongst an array of strings.
If there is no common prefix, return an empty string “”.

Example 1:

Input: [“flower”,“flow”,“flight”]
Output: “fl”

Example 2:

Input: [“dog”,“racecar”,“car”]
Output: “”
Explanation: There is no common prefix among the input strings.

Note:

All given inputs are in lowercase letters a-z.

算法

可用分治算法

代码

char* common(char* left_str, char* right_str){
    
    int min_len = strlen(left_str);
    if(strlen(right_str) < min_len){
        min_len = strlen(right_str);
    }
    
    int i;
    char* result = (char *)malloc(10000 * sizeof(char));
    int num = 0;
    for(i = 0; i < min_len; i++){
        if(left_str[i] == right_str[i]){
            result[num++] = (left_str[i]);
        }else{        
            break;
        }
    }
    result[num++] = '\0';
    return result;
}
char* longestCommonPrefix_left_right(char** strs,int strsSize,int left, int right){
    if(left == right){
        return strs[left];
    }
    int mid = (left + right) / 2;
    
    
    char* lcp_left = longestCommonPrefix_left_right(strs, strsSize, left, mid);
    char* lcp_right= longestCommonPrefix_left_right(strs, strsSize, mid + 1, right);
    return common(lcp_left, lcp_right);
    
    
}
    


char* longestCommonPrefix(char** strs, int strsSize) {
    if(strsSize == 0){
        char* p = "";
        return p;
    }else{
        return longestCommonPrefix_left_right(strs, strsSize, 0, strsSize-1);
    }
    
}