牛客热题：最长回文子串

📟作者主页：慢热的陕西人

🌴专栏链接：力扣刷题日记

📣欢迎各位大佬👍点赞🔥关注🚓收藏，🍉留言

牛客热题：最长回文子串

题目链接

最长回文子串_牛客题霸_牛客网 (nowcoder.com)

方法一：动态规划

思路

①状态表示：

$dp[i][j]$表示以A[i],A[j]为头尾的字符串是否是回文字符串的状态

②状态转移方程：

当A[i] 和 A[j] 相等的情况下：

$dp[i][j]=dp[i+1][j-1]$

③初始化：

循环内部会直接对长度为1的区间直接修改为状态为true

④填表顺序：

最外层：字符串的长度从短到长

内部：i，也就是起始位置从左到右即可

⑤返回值：

在循环的过程中，$dp[i][j]$为真的话就更新当前的$res=len+1$;

最后返回res即可

代码

int getLongestPalindrome(string A) 
    {
        int n = A.size();
        int res = 0;
        vector<vector<bool>> dp(n, vector<bool>(n, false));

        for(int len = 0; len < n; ++len)
        {
            for(int i = 0; i < n - len; ++i)
            {
                int j = i + len;

                if(A[i] == A[j])
                {
                    if(len <= 1)
                    {
                        dp[i][j] = true;
                    }
                    else 
                    {
                        dp[i][j] = dp[i + 1][j - 1];
                    }

                    if(dp[i][j])
                    {
                        res = len + 1;
                    }
                }
            }
        }

        return res;
    }

复杂度

时间复杂度：$O(N^2)$,首先枚举从0到n - 1 的长度的字符串

空间复杂度：$O(N^2)$,利用了额外的dp数组，来存储对应的状态