[力扣_14] 最长公共前缀

题目入口:点击进入

相关算法:

  • 横向扫描——时间复杂度O(mn),空间复杂度O(1);
  • 列向扫描——时间复杂度O(mn),空间复杂度O(1);
  • 二分法——时间复杂度O(mn),空间复杂度O(m log n);
  • 分治法——时间复杂度O(mn log mn),空间复杂度O(mn log mn)

这里详细介绍横向扫描和列向扫描的解法,分治和二分可以去官方题解上去看。

横向扫描

根据题目意思,我们可以知道,最长公共前缀的长度绝对不会长于字符串数组中最小字符串的长度,则不管字符串数组中字符串长度是如何排序的,我们都可以将的第一个字符串作为基准,然后去与后面的字符串做比较,逐步保留相同的字符

注意特判:当字符数组长度为0时,返回"",当字符数组为时,返回它本身

img

img

img

img

代码如下所示:

void SubString(char* t,char *s,int pos,int len)
{
    int i=0;
    for(int j=pos;j<pos+len;j++,i++)
    {
        t[i]=s[j];
    }
    t[i]='\0';
}
char* longestCommonPrefix(char ** strs, int strsSize){
    if(strsSize==0) return "";  //如果字符串数组为空,直接返回""
    char *ReturnArray=(char*)malloc(sizeof(char)*(strlen(strs[0])+1));
    strcpy(ReturnArray,strs[0]);
    for(int i=1;i<strsSize;i++)
    {
       int j=0;
       while(j<strlen(ReturnArray))
       {
           if(strs[i][j]!=ReturnArray[j])
           break;
           j++;
       }
       SubString(ReturnArray,strs[i],0,j);
    }
    return ReturnArray;
}

列向扫描

除了上述方法,我们还可以一列一列的扫描,直到发现不等的时候,则退出循环,返回数组,依旧拿第一个字符串作为基准对之后的字符串的每一个字符去做判断

上述动画演示采用大佬的C++题解,在C语言中,没有minstr函数,则我们依旧拿第一个字符串作为基准去判断,思路类同

代码如下所示:

char * longestCommonPrefix(char ** strs, int strsSize){
    if(strsSize==0) return "";  //如果字符串数组为空,直接返回""
    char *ReturnArray=(char*)malloc(sizeof(char)*(strlen(strs[0])+1));
    strcpy(ReturnArray,strs[0]);
    int sign=0;//初始化哨兵
    for(int i=0;i<strlen(ReturnArray);i++)
    {
       int j=1;
       while(j < strsSize)
       {
           if(strs[j][i]!=ReturnArray[i]){
           sign=1;//哨兵,当当前字符不等时,则退出
           break;
           }
           j++;
       }
       if(sign)
       {
           ReturnArray[i]='\0';
           return ReturnArray;
       }
    }
    return ReturnArray;
}

关于分治和二分的解法,由于时间复杂度还高,则我并不打算写出来,只了解思路即可,在官方题解中将这两种方法的思路讲解的很清晰,[点击这句话即可进入](

本文链接:

https://nullcode.fun/60.html
1 + 8 =
快来做第一个评论的人吧~