[力扣_5] 最长回文子串

题目入口:点击进入

相关算法:

  • 暴力枚举,时间复杂度O(n³),空间复杂度O(1)
  • 中心扩散,时间复杂度O(n²),空间复杂度O(1)
  • 动态规划,时间复杂度O(n²),空间复杂度O(n²)——解题思路

中心扩散法

这个算法很好理解,我们知道,回文串一定是对称的,所以我们每次循环可以选择一个中心,进行左右扩展,判断左右字符是否相等即可

枚举可能出现的回文子串的“中心位置”,从“中心位置”尝试尽可能扩散出去,得到一个回文串

因此中心扩散的思路是:遍历每一个索引(下标),以这个索引为中心,利用“回文串”中心对称的特点,往两边扩散,看最多能扩散多远

枚举“中心位置”的时间复杂度为O(N),从“中心位置”扩散得到“回文子串”的时间复杂度为O(N),因此时间复杂度可以达到O(N²)

在这里要注意一个细节:回文串在长度为奇数和偶数的时候,“回文中心”的形式是不一样的

  • 奇数回文串的“中心”是一个具体的字符,例如:回文串“aba”的中心是字符“b”
  • 偶数回文串的“中心”是位于中间两个字符的“空隙”例如:回文串串“abba”的中心是两个“b”中间的那个“空隙”

所以在每次判断最长回文子串的时候,需要进行奇偶的两种情况的不同判断:

img

我们可以设计一个方法,兼容以上两种情况:

  1. 如果传入重合的索引编码(下标),进行中心扩散,此时得到的回文子串的长度是奇数
  2. 如果传入相邻的索引编码(下标),进行中心扩散,此时得到的回文子串的长度是偶数

如果对上述有所疑惑,可以观看:大佬视频 再对照下述代码就可以加快理解

C语言答题代码:

int GetLongstPalindrome(char* s, int l, int r)//从给定中心点判断是否为回文
{
    while (l >= 0 && r < strlen(s) && s[l] == s[r])
    {
        l--;
        r++;
    }

    return r - l - 1;//这里可以在本子上计算一下
}
char * longestPalindrome(char * s){
    int maxlen = 0, curmax, start;
    int temp1, temp2;
    int sleng = strlen(s);
    if(sleng<2)
    {
        return s;
    }
    for (int i = 0; i < sleng; i++)
    {
        temp1 = GetLongstPalindrome(s, i, i);//当字符串为奇数传入重复字符作为中心点
        temp2 = GetLongstPalindrome(s, i, i + 1);//当子串为偶数传入相邻字符作为中心点
        curmax = temp1 > temp2 ? temp1 : temp2;//取两个函数返回的最大值
        if (curmax > maxlen)
        {
            maxlen = curmax;//更新最大长度
            start = i - ((maxlen + 1) / 2) + 1;//取到此子串在主串中的位置,可以在纸上画一下方便理解
        }

    }
    char* ReturnStr = (char*)malloc(sizeof(char) * maxlen + 1);
    for (int i = start, p = 0; p < maxlen; i++, p++)
    {
        ReturnStr[p] = s[i];//截取子串,相当于SubString
    }
    ReturnStr[maxlen] = '\0';


    return ReturnStr;
}

动态规划(由最长公共子串得来)

利用回文串的特性,正着读和反着读都一样,我们可以将字符串倒置过来作为模式串与给定的字符串去求的它们的最长相等子串

状态转移性质:子串是相邻的,前一个与其相等,后一个是在前一个的基础上+1

例如:S=“caba”,S'="abac",最长的相等子串就是“aba”,所以原字符串的最长回文串就是“aba”

整体思想是:申请一个二维数组初始化为零作为这个问题的状态转移过程

状态转移方程为:dpi=dpi-1+1;

当i(行)和j(列)为0的时候单独分析,字符相等的话dpi就为1

而dp数组中的每一个分量保存的就是当前字符串匹配子串的长度,如下图所示:

img

这儿需要注意判别一个特殊情况:

例如:S=“abc435cba”,S=“abc534cba”,最长公共子串是“abc”和cba,但是显然这两个字符串都不是回文串

所以我们求出最长相等子串后,并不一定是回文串,我们还需要判断该字符串倒置前的下标和当前的字符串下标是不是匹配

比如 S="caba",S'="abac" ,S’ 中 aba 的下标是 0 1 2 ,倒置前是 3 2 1,和 S 中 aba 的下标符合,所以 aba 就是我们需要找的。当然我们不需要每个字符都判断,我们只需要判断末尾字符就可以。

img

首先 i,j 始终指向子串的末尾字符。所以 j 指向的红色的 a 倒置前的下标是 beforeRev = length-1-j=4-1-2=1,对应的是字符串首位的下标,我们还需要加上字符串的长度才是末尾字符的下标,也就是 beforeRev+arri-1=1+3-1=3,因为 arri 保存的就是当前子串的长度,也就是图中的数字 3。此时再和它与 i 比较,如果相等,则说明它是我们要找的回文串。

之前的 S="abc435cba",S'="abc534cba",可以看一下图示,为什么不符合。

img

当前 j 指向的 c,倒置前的下标是 beforeRev=length-1-j=9-1-2=6,对应的末尾下标是beforeRev+arri-1=6+3-1=8,而此时 i=2,所以当前的子串不是回文串。

C语言测试代码如下所示:

char * longestPalindrome(char * s){
   int sleng=strlen(s);
   int dp[sleng][sleng];
   

   int maxlen=0,left,right;
   int beforeRve;
   for(int j=sleng-1,m=0;j>=0;j--,m++){
       for(int i=0,n=0;i<sleng;i++,n++){
           if(s[i]==s[j]){
             if(m==0||n==0){
                 dp[m][n]=1;
             }
             else{
                 dp[m][n]=dp[m-1][n-1]+1;
             }
           }
           else{
               dp[m][n]=0;
           }
          if(dp[m][n]>maxlen)
          {
            beforeRve=sleng-1-m;
            if(beforeRve+dp[m][n]-1==n){
                maxlen=dp[m][n];
                left=j;
                right=i;
            }
          }
       }
   }

   char *temp=(char*)malloc(sizeof(char)*maxlen+1);
   for(int i=left,p=0;i<=right;i++,p++){
       temp[p]=s[i];
   }
   temp[maxlen]='\0';
   return temp;
}

之前我们求过最长重复子串,这个跟最长重复子串的思路很像,绕就绕在:判断是否链接的是同一字符串,因为反过来的时候如同上边那个例子,首尾有相等子串但该子串不是回文

就需要找到倒置前的位置再加上已匹配的长度去去判断它主串匹配字符的位置是否一致,如果不一致,则取自不同子串。

动态规划(由回文性质得)

[动态规划]的一个关键步骤是想清楚[状态如何转移],事实上,[回文]天然具有[状态转移]的性质

  • 一个回文去掉两头以后,剩下的部分依然是回文(这里暂时不考虑边界情况)

依旧从回文串的定义展开讨论:

  • 如果一个字符串的头尾两个字符都不相等,那么这个字符串一定不是回文串
  • 如果一个字符串的头尾两个字符相等,才有必要继续判断下去

    • 如果里面的子串也是回文,则整体就是回文串
    • 如果里面的子串不是回文串,整体就不是回文串

即:在头尾字符相等的情况下,里面子串的回文性质据定了整个子串的回文性质,这就是状态转移,因此可以把[状态]定义为原字符串的一个子串是否为回文串

第一步:定义状态

dpi表示子串s[i...j]是否为回文子串,这里子串s[i...j]定义为左闭右闭区间,可以取到s[i]和s[j]

第二步:思考状态转移方程

在这一步分类讨论(根据头尾字符是否相等),根据上面的分析得到

dp[i][j] = (s[i]==s[j]) and dp[i+1][j-1]

说明:

  • [动态规划]事实上是在填一张二维表格,由于构成子串,因此i和j的关系是i<=j,因此i和j的关系是i <= j,因此,只需要填这张表格对角线以上的部分
  • 看到dpi+1就得考虑边界情况

边界条件是:表达式[i+1,j+1]不构成区间即长度严格小于2,即j-1-(i+1)+1<2,如:ab,整理得:j-i<3

这个结论很显然:j-i<3等价于j-i+1<4,即当子串s[i...j]的长度等于2或者等于3的时候,其实只需要判断一下头尾两个字符是否相等就可以直接下结论

  • 如果子串s[i+1...j-1]只有一个字符,即去掉两头、剩下中间部分只有一个字符,显然是回文
  • 如果子串s[i+1...j-1]为空串,那么子串s[i,j]一定是回文字符串

因此,在s[i]==s[j]成立和j-i<3的前提下,直接可以下结论,dp[i][j]=true,否则才执行状态转移。

第三步:考虑初始化

初始化的时候,单个字符一定是回文串,因此把对角线先初始化为true,即dp[i][i]=ture

事实上,初始化的部分都可以省去,因为只有一个字符的时候一定是回文,dp[i][i]根本不会被其他状态所参考,但是为了代码的严谨性,在此代码中不省去

第四步:考虑输出

只要一得到dp[i][j]=true,就记录子串的长度和起始位置,没有必要截取,这是因为截取字符串也要消耗性能,记录此时的回文子串的[起始位置]和[回文长度]即可

第五步:考虑优化空间

因为在填表过程中,只参考了左下方的数值,事实上可以优化,但是增加了代码编写和理解的难度,丢失可读性和可解释性,在这里不优化空间

注意事项

总是先得到小子串的回文判定,然后大子串才能参考小子串的判断结果,即填表顺序很重要

是先列后行,行要小于列,换句话说,就是一列一列的填写上半部分的状态,图如下所示:

img

此题填表地址:点击进入

代码如下所示:

char * longestPalindrome(char * s){
  
   int sleng=strlen(s);
   if(sleng<2)//当只有一个字符时;
   {
       return s;
   }
   int dp[sleng][sleng];
   for(int i=0;i<sleng;i++){
       dp[i][i]=1;
   }
   int left,right,maxlen=1,curlen,start=0;
   for(int j=1;j<sleng;j++)
   {
       for(int i=0;i<j;i++)
       {
          if(s[i]!=s[j]){//当头尾不相等时
             dp[i][j]=0;//子串不相等
          }
          else
          {
              if(j-i<3){
                  dp[i][j]=1;//子串相等
              }//当只有两个字符或没得字符时
              else{
                  dp[i][j]=dp[i+1][j-1];//当中间有多个字符时,等于取出头尾后的子串的状态
              }
          }
          //一旦dp[i][j]为1,在[i...j]这个区间里就是回文
          if(dp[i][j])
          {
              curlen=j-i+1;
              if(curlen>maxlen)
              {
                  maxlen=curlen;
                  start=i;
              }
          }
       }
   }
   //以下等同于SubString
    char *temp=(char*)malloc(sizeof(char)*maxlen+2);
    int p=0;
    for(int i=start;p<maxlen;i++)
    {
        temp[p]=s[i];
        p++;
    }
    temp[maxlen]='\0';
    return temp;
}

通过图结合代码可以发现:

  • 当i和j的差距小于或等于3的时候,dp值可以直接判断,不用参考以前的dp值
  • 其他情况,每当计算新dp值得时候,都一定会参考[左下角]的dp值,即dp[i+1][j-1](i+1表示在下边,j-1表示在左边)

因此,从上到下写,或者从下到上写都是可以的(代码中是从上到下的思路)

总结:

  • 我们看到,用动态规划解决问题时,有的时候并不是直接面向问题的
  • 动态规划依然是【空间换时间】思想的体现,并且本身动态规划作为一种打表格法,就是在用空间换时间

动态规划本质上还是BF算法,因为枚举左右边界有O(N²)那么多

本文链接:

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