每周一道算法题(十)

本周的算法题难度级别依旧是'Easy',也很简单

题目：找出所有字符串中最长的公共前缀

思路:提供两个思路，一个思路是两个两个字符串进行比较，取出公共的前缀位数再和下一个字符串比较。另一个思路就是把第一个字符串的每一个字母分别和剩下所有的字符串的每一个字母比较

代码：

//思路一：
char* longestCommonPrefix(char** strs, int strsSize) {
    if (strsSize == 0) return "";
    if (strsSize == 1) return *strs;
    //取第一个字符串的长度
    int len = strlen(strs[0]);
    for (int i = 0;i < strsSize - 1;i++) {
        //取当前的字符串和下一个字符串长度短的长度
        int tempLen = strlen(strs[i]) < strlen(strs[i+1]) ? strlen(strs[i]) : strlen(strs[i+1]);
        for (int j = 0;j < tempLen && j < len;j++) {
            //比较当前字符串和下一个字符串的元素是否一样，如果不一样，记录数字
            if (strs[i][j] != strs[i+1][j]) {
                len = j;
                break;
            }
        }
        //取短的长度
        len = len < tempLen ? len : tempLen;
    }
    if (len == 0) return "";
    char *result = malloc(len+1);
    //记录第一个字符串公共的部分
    for (int i = 0;i < len; i++)
        result[i] = strs[0][i];
    result[len] = '\0';
    return result;
}

//思路2
char* longestCommonPrefix(char** strs, int strsSize) {
    if (strsSize == 0) return "";
    if (strsSize == 1) return *strs;
    //stop：是否停止循环 len:公共长度
    int stop = 0,len = 0;
    for (;len < strlen(*strs); len++ ) {
        for (int i = 1;i < strsSize;i++) {
            //比较所有字符串的共同位置，如果不相同或者长于某一个字符串的长度则停止循环 返回字符串
            if (strs[0][len] != strs[i][len] || len > strlen(strs[i])) {
                stop = 1;
                break;
            }
        }
        if (stop) break;
    }
    if (len == 0) return "";
    char *result = malloc(len+1);
    for (int i = 0;i < len; i++) 
        result[i] = strs[0][i];
    result[len] = '\0';
    return result;
}

这题的思路很简单，但实现起来确会出现很多问题，比如内存之类的，C语言真不好用。。。

版权声明：本文为 Crazy Steven 原创出品，欢迎转载，转载时请注明出处!