LeetCode-简单-14-最长公共前缀(C)

昨天刷题做二阶字符串指针的时候又出问题了,所以今天换了个简单难度的题。

结果结果!

我又出问题了!

可恶!

不过解决了:C语言二级字符串指针的使用(函数传参/长度获取/空间分配) 

题目

编写一个函数来查找字符串数组中的最长公共前缀。

如果不存在公共前缀,返回空字符串 “”。

示例 1:

输入: [“flower”,”flow”,”flight”]
输出: “fl”
示例 2:

输入: [“dog”,”racecar”,”car”]
输出: “”
解释: 输入不存在公共前缀。
说明:

所有输入只包含小写字母 a-z 。

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/longest-common-prefix
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

思路

这次代码厉害了,五次提交,四次0ms。

两层循环。

第一层循环:遍历第一个字符串的每个字符,即strs[0][0]~strs[0][n],因为是取公共前缀,所以无论如何,公共前缀必然包括在strs[0]中,因此直接遍历strs[0]即可。
遍历变量为grepPosition。

第二层循环:遍历每个字符串的第grepPosition个字符,与第一个字符串的第grepPosition个字符对比,如果不相同就直接返回已合成的公共前缀字符串longestPrefix。

第二层循环的目的是比较是否相同,如果都相同,那么就将这个相同的字符添加到公共前缀longestPrefix末尾,因为只要添加一个字符,因此直接修改即可,不用strcat之类的拼接函数。
但添加完需要在末尾新添加’ \0′ 结束符,不然在第二层循环中的返回可能出错。

代码

char * longestCommonPrefix(char ** strs, int strsSize){
    char *longestPrefix;
    int grepPosition, arrayPosition;
    longestPrefix = (char*)malloc(sizeof(char));
    longestPrefix[0] = '\0';
    if(strsSize==0) return longestPrefix;
    for(grepPosition=0; strs[0][grepPosition]!='\0';  grepPosition++){
        for(arrayPosition=1;    arrayPosition<strsSize; arrayPosition++){
            if(strs[0][grepPosition]!=strs[arrayPosition][grepPosition]){
                return longestPrefix;
            }
        }
        longestPrefix = (char*)realloc(longestPrefix, (grepPosition+2)*sizeof(char));
        longestPrefix[grepPosition] = strs[0][grepPosition];
        longestPrefix[grepPosition+1] = '\0';
    }
    return longestPrefix;
}

You may also like...

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注