最长回文子串-LeetCode5 动态规划_最长回文子串动态规划-CSDN博客

本文链接：https://blog.csdn.net/Postlude/article/details/134193852

文章介绍了使用暴力法和动态规划算法解决最长回文子串问题的过程，暴力法的时间复杂度为O(n^3)，而动态规划法将时间复杂度降低到O(n^2)，空间复杂度同样为O(n^2)。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

在这里插入图片描述

由于基础还不是很牢固一时间只能想到暴力的解法:

取遍每个子串总数量n+n-1+n-2+…+1 =O(n^2)
判断每个子串是否属于回文串 O(n)
故总时间复杂度为O(n^3)

class Solution {
public:
    string longestPalindrome(string s) {
int max=0;
    string ret;
    for(int i=0;i<s.size();i++)
        for(int j=1;j<=s.size()-i;j++)
        {
            string s1=s.substr(i,j);
            if(Judeg(s1)>max)
            {
                max=Judeg(s1);
                ret=s1;
            }
                
        }
    return ret;
    }

int Judeg(string s)
{
    int i,j;
    for(i=0,j=s.size()-1;i<=j;i++,j--)
    {
        if(s[i]!=s[j])
            return 0;
    }
    return s.size();
}
};

在查阅题解以后比较简单易懂的还是动态规划算法
设某子串的左下标为i 右下标为j
则该子串是不是回文串可以走如下流程:
1.s[i]和s[j]不相等那么一定不是回文子串 dp[i][j]=false
2.在s[i]和s[j]已经相等的基础上若子串的长度<=3 那么一定是回文串 dp[i][j]=true
3.最后一种情况 dp[i][j]=dp[i+1][j-1]
一个很长的子串是不是回文串取决于去掉首尾字符以后中间的子串是不是回文串(动态规划套娃)

时间复杂度为遍历dp数组故为O(n^2)
空间复杂度为开辟dp数组故为O(n^2)

string longestPalindrome(string s) 
{
    int max=1,begin=0;
    int len=s.size();
    if(len<2)
        return s;
    
    bool **dp=new bool*[len];
    for(int i=0;i<len;i++)
    {
        dp[i]=new bool [len];
    }

    for(int j=1;j<len;j++)
    {
        for(int i=0;i<j;i++)
        {
            if(s[i]!=s[j])
                dp[i][j]=false;
            else
            {
                if(j-i+1<=3)
                    dp[i][j]=true;
                else
                {
                    dp[i][j]=dp[i+1][j-1];
                }
            }

            if(dp[i][j]&&j-i+1>max)
            {
                max=j-i+1;
                begin=i;
            }
        }
    }

    return s.substr(begin,max);
}