📟作者主页:慢热的陕西人
🌴专栏链接:力扣刷题日记
📣欢迎各位大佬👍点赞🔥关注🚓收藏,🍉留言
文章目录
- 牛客热题:最长回文子串
- 题目链接
- 方法一:动态规划
- 思路
- 代码
- 复杂度
牛客热题:最长回文子串
题目链接
最长回文子串_牛客题霸_牛客网 (nowcoder.com)
方法一:动态规划
思路
①状态表示:
d p [ i ] [ j ] dp[i][j] dp[i][j]表示以A[i],A[j]为头尾的字符串是否是回文字符串的状态
②状态转移方程:
当A[i] 和 A[j] 相等的情况下:
d p [ i ] [ j ] = d p [ i + 1 ] [ j − 1 ] dp[i][j] = dp[i + 1][j - 1] dp[i][j]=dp[i+1][j−1]
③初始化:
循环内部会直接对长度为1的区间直接修改为状态为true
④填表顺序:
最外层:字符串的长度从短到长
内部:i,也就是起始位置从左到右即可
⑤返回值:
在循环的过程中, d p [ i ] [ j ] dp[i][j] dp[i][j]为真的话就更新当前的 r e s = l e n + 1 res = len + 1 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 ) O(N ^ 2) O(N2),首先枚举从0到n - 1 的长度的字符串
空间复杂度: O ( N 2 ) O(N^2) O(N2),利用了额外的dp数组,来存储对应的状态