牛客热题：最长回文子串

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

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

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

牛客热题：最长回文子串

题目链接

最长回文子串_牛客题霸_牛客网 (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数组，来存储对应的状态