国外做的比较的ppt网站,长沙网站设计服务商,专注专业网站建设,做站群一个网站多少钱#x1f4df;作者主页#xff1a;慢热的陕西人 #x1f334;专栏链接#xff1a;力扣刷题日记 #x1f4e3;欢迎各位大佬#x1f44d;点赞#x1f525;关注#x1f693;收藏#xff0c;#x1f349;留言 文章目录 牛客热题#xff1a;最长回文子串题目链接方法一作者主页慢热的陕西人 专栏链接力扣刷题日记 欢迎各位大佬点赞关注收藏留言 文章目录 牛客热题最长回文子串题目链接方法一动态规划思路代码复杂度 牛客热题最长回文子串
题目链接
最长回文子串_牛客题霸_牛客网 (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[i1][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 reslen1;
最后返回res即可
代码
int getLongestPalindrome(string A) {int n A.size();int res 0;vectorvectorbool dp(n, vectorbool(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数组来存储对应的状态
