我要招人

去企业版

首页 > 试题广场 >

最长公共前缀

[编程题]最长公共前缀

热度指数：159173 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给你一个大小为 n 的字符串数组 strs ，其中包含n个字符串 , 编写一个函数来查找字符串数组中的最长公共前缀，返回这个公共前缀。

数据范围： $0 \le n \le 5000$ ， $0 \le len(strs_i) \le 5000$

进阶：空间复杂度 $O(1)$ ，时间复杂度 $O(n*len)$

示例1

输入

["abca","abc","abca","abc","abcc"]

输出

"abc"

示例2

输入

["abc"]

输出

"abc"

算法知识视频讲解

无名珠

char* longestCommonPrefix(char** strs, int strsLen ) {
    if (strsLen == 0) return ""; //字符串为空，返回空

    for (int col=0; strs[0][col]!='\0'; ++col)
    {
        //逐行比较
        for (int row=1; row<strsLen; ++row) //row=1不能省略
        {
            if (strs[0][col] != strs[row][col])
            {
                strs[0][col] = '\0'; //截断一样的部分
                return strs[0]; //部分一样
            }
        }
    }
    return strs[0]; //完全一样
}

发表于 2024-05-29 20:56:41 回复(0)

牛客183552821号

真麻烦，空数据要返回空还不能是null。。。

/**

* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可

* @param strs string字符串一维数组

* @param strsLen int strs数组长度

* @return string字符串

#include <stdlib.h>

char* longestCommonPrefix(char** strs, int strsLen ) {

// write code here

if(strsLen==1)

return strs[0];

if(strsLen==0)

return "";

if(**strs=="")

return "";

char* buffer;

int lx=0;

for(int i=0;i<strsLen;i++)

{

int ii=0;

while (*(*(strs+i)+ii)!='\0') {

ii++;

if(ii>lx)

{lx=ii;}

}

for(int ii=0;ii<lx+1;ii++)

{

for(int i=0;i<strsLen;i++)

{

if(*(*(strs)+ii)==*(*(strs+i)+ii))

{}

else {

*(*(strs)+ii)='\0';

return strs[0];

}

return strs[0];

}

编辑于 2024-03-24 11:23:25 回复(0)

一个优雅的程序猿

char* longestCommonPrefix(char** strs, int strsLen ) {
    int str_lengthmin_LOC, str_lengthmin, i,j;
    char* str;
   
    if(strsLen==0)
        return "";
    else if(strsLen==1)
        return strs[0];

    str_lengthmin_LOC=0;
    for(i=0; i<strsLen; i++) {
        if(strlen(strs[i]) < strlen(strs[str_lengthmin_LOC]))
            str_lengthmin_LOC = i;
    }
    str = (char*)malloc(strlen(strs[str_lengthmin_LOC])+1);
    str_lengthmin = strlen(strs[str_lengthmin_LOC]);
    //printf("strsLen:%d str_lengthmin_LOC:%d\n", strsLen, str_lengthmin_LOC);

    for(i=str_lengthmin; i>0; i--) {
        for(j=0; j<strsLen; j++) {
            //printf("i:%d j:%d str:%s %s\n", i,j,strs[j],strs[str_lengthmin_LOC]);
            if(strncmp(strs[j], strs[str_lengthmin_LOC], i))
                break;
        }
        if(j==strsLen){
            strncpy(str,strs[str_lengthmin_LOC],i);
            str[i] = 0;
            //printf("over, i:%d j:%d str:%s\n", i,j,str);
            return str;
        }
    }
    return "";
}

编辑于 2024-03-13 15:29:19 回复(0)

陈让然

看清题目要求，求最长公共前缀，那么就简单了，这题C代码我做的时候只有4条

char* longestCommonPrefix(char** strs, int strsLen ) {
    // write code here
    //如果字符串为空，返回空
    if (strsLen == 0) 
    {
        return "";
    }
    //求第一个字符串的长度
    int len = strlen(strs[0]);
    //与第一个字符串的每个字符做对比，以此为基准
    for (int i = 0; i < len; i++) {
        char c = strs[0][i];
        //将其他段的字符对应位置的字符进行比较
        for (int j = 1; j < strsLen; j++) 
        {
            //如果对应位置字符不相同
            //说明在这之前的都是相同的前缀字符
            if (strs[j][i] != c) 
            {
                //截断前缀
                strs[0][i] = '\0';
                //返回前缀
                return strs[0];
            }
        }
    }
    //所以字符串都相同
    return strs[0];
}

发表于 2023-09-14 17:17:01 回复(0)

80后大叔

挨个对比前缀字符即可

char* longestCommonPrefix(char** strs, int strsLen ) {
    // write code here
    if(strsLen == 0) return "";
    if(strlen(strs[0])==0) return "";
    int min = strlen(strs[0]);
    for(int i=0; i<strsLen; i++){
        if(min>strlen(strs[i])) min=strlen(strs[i]);
    }
    char* ret = (char*)malloc(sizeof(char)*(min+1));
    if(ret==NULL) return NULL;
    int num=0;
    for(int j=0; j<min;j++) {
        int flag=0;
        for(int i=1; i<strsLen; i++) {
            if(strs[i][j]!=strs[i-1][j]) {
                flag=1;
                break;
            }
        }
        if(flag==0) ret[num++]=strs[0][j];
        else break;
    }
    ret[num]='\0';
    return ret;
}

发表于 2022-11-10 15:42:04 回复(0)

牛客310270168号

char* longestCommonPrefix(char** strs, int strsLen ) {
// write code here
int len=strlen(strs[0]);
if(strsLen == 0) return "";
if(strsLen==1)
{
return strs[0];
}
int flag=1;
char* result=(char*)calloc(len, sizeof(char));
int i,j,k;
for(i=0;flag;i++)
{
for(j=1;j<strsLen;j++)
{
if(strs[j][i]!=strs[0][i])
{
flag=0;
break;
}
}
}
for(k=0;k<i-1;k++)
{
result[k]=strs[0][k];
}
return result;
}

发表于 2022-08-30 17:38:58 回复(0)

牛客633185646号

static char* min(char** strs, int strsLen){
    char *ps[strsLen],*tp;
    int N = strsLen;
    for(int i = 0;i < strsLen;i++)
        ps[i] = strs[i];
    int min = strlen(ps[0]);
    tp = ps[0];
    for(int i = 0;i < strsLen;i++){
      if(strlen(ps[i]) < min){
          min = strlen(ps[i]);
          tp = ps[i];
      }  
    }
    return tp;
}
char* longestCommonPrefix(char** strs, int strsLen ) {
    if(!strsLen)return "";
    char* s;
    s = min(strs,strsLen);
    int m = strlen(s);
    for(int i = 0; i < strsLen; i++){
        for(int j = 0; j < m; j++){
            if(s[j] != strs[i][j])
             m = j;   
        }
    }
    char* ss = (char*)malloc(m*sizeof(char));
    for(int i = 0; i < m ; i++ )
        ss[i] = s[i];
    ss[m] = '\0';
    return ss;
}

发表于 2022-07-19 19:27:31 回复(0)