LeetCode第14题: longestCommonPrefi

上一题：LeetCode第13题: romanToInt(C语言）

1、基本方法
思路：以第一个子数组为参考base，从0开始固定base的下标 j ，从1开始循环遍历strs的每个子数组strs[i]，并比对strs子数组的对应下标元素strs[i][j]与base[j]，相等则i++, 比对下一个子数组，不相等则退出循环。当i == strsSize时，表明每个子数组的j下标元素均相等，下标 j += 1。否则，直接退出。

char* longestCommonPrefix(char** strs, int strsSize) {
    if(strsSize == 0)
        return "";
    else if(strsSize == 1)
        return strs[0];
    
    int i = 1, j = 0;
    char *base = strs[0];
    while(1){
        while(i < strsSize && base[j] && strs[i][j] && base[j] == strs[i][j]){
            i++;
        }
        if(i == strsSize){
            j++;
            i = 1;
        }
        else{
            base[j] = '\0';
            break;
        }
    }    
    return base;
}

2、分治方法
思路：计算strsSize的中位数，然后以中位数mid将strs拆分为两个子数组，然后分别将两个子数组递归求解，直到每个子数组的长度为2，则进行实际的计算。最后递归返回计算结果，然后进行结果合并。

char* longestCommonPrefix(char** strs, int strsSize) {
    if(strsSize == 0)
        return "";
    else if(strsSize == 1)
        return strs[0];

    int mid = (strsSize + 1) / 2;
    char *first = longestCommonPrefix(strs, mid);
    char *second = longestCommonPrefix(strs + mid, strsSize - mid);
    int j = 0;
    while(first[j] && second[j] && first[j] == second[j])
        j++;
    first[j] = '\0';
    return first;
}

本系列文章，旨在打造LeetCode题目解题方法，帮助和引导同学们开阔学习算法思路，由于个人能力和精力的局限性，也会参考其他网站的代码和思路，如有侵权，请联系本人删除。
下一题：LeetCode第15题: threeSum(C语言）