文章目录1 .主题2 .解题2.1自己写的DP2.2优化后的DP2.3中心扩张法
1 .主题
指定字符串s，找到s的最长的回文子串。 可以假设s的最大长度为1000。
示例输入： 'babad '输出： 'bab '也是有效的答案。 例2 )输入：(cbbd )输出：(cbbd )源：输入按钮(LeetCode ) )。
链接： https://leet code-cn.com/problems/longest-palindromic-substring
版权归互联网所有。 商业转载请联系官方许可证。 非商业转载请注明出处。
2 .解决问题的相似主题： LeetCode 1216 .验证回文字符串iii(DP )
LeetCode 1312 .使字符串成为回文串的最小插入次数(区间DP ) ) ) ) ) )。
LeetCode 647 .回文子字符串(DP ) ) ) ) ) ) ) )。
LeetCode 516 .最长回文子序列(动态规划)
2.1自己写的DP自己写的DP效率很低，o(n2 ) o ) n^2) o(n2 ) n ) n ) n2)时间复杂度从长度1开始遍历子串的长度。 具体而言，注释class solution (public 3360 stringlongestpalindrome ) strining if(n=1) return s； 字符串ans； 矢量向量(NDP (n，vectorint ) n，0 )； 向量工具(nsame (n，vectorbool ) n，false )； //区间[i，j]的最大回文长度for(I=0； i n； I ) { dp[i][i]=1； //单个字符为回文same[i][i]=true； //区间内的文字都相同吗}for(len=1； len n； len () for ) I=0； i n-len； I () if ) DP[I][Ilen-1] ) /【I，i len-1】是回文串(if(same[I](Ilen-1 ) ) /区间内全部相同)//奇数字符回文-----------------。 (if ) s[I-1]==s[Ilen] ) /左右各一个) if ) s[I-1]==s[I] ) same[i-1][i len]=true； dp[i-1][i len]=2 dp[i][i len-1]； }if(s[Ilen]==s[I] ) /在右边增加一个(DP[I][Ilen]=1DP[I] ) Ilen-1； same[i][i len]=true； } } else//区间[i，i len-1]内的字符不同，{if(I-1=0s(I-1 )==s (ilen ) ) DP (I-1 ) ) ilen (=2dp ) I ) ans=s.substr(I-1，maxLen )； (if ) DP[I-1][Ilen]maxlen ) { maxLen=dp[i-1][i len]； ans=s.substr(I-1，maxLen )； }if(DP[I][Ilen-1]maxlen ) { maxLen=dp[i][i len-1]； ans=s.substr(I，maxLen )； }if(DP[I][Ilen]maxlen ) { maxLen=dp[i][i len]； ans=s.substr(I，maxLen )； } }返回ans； }； 1440 ms 202.3 MB，打破了5% cpp
2.2优化后的DP在上述基础上，初始化时先用一个字、两个字的回文进行class solution { public 3360 stringlongestpalindrome (strings ) if ) s.size )=1) REE stringans=s.substr (0，1 )； 向量球(NDP (n，向量球) n，0 )； for(I=0； i n； I ) { dp[i][i]=true； if(In-1s[I]==s[I1] ) { dp[i][i 1]=true； if(Maxlen2) Maxlen=2； ans=s.substr(I，2 )； }}for(len=1； len n； len () for ) I=0； i n-len； I () if ) DP [ I ] [ ilen-1 ] I-1=0s [ I-1 ]==s [ ilen ] ) /是回文串) { dp[i-1][i len]=true； if(Len2Maxlen ) { maxLen=len 2； ans=s.substr(I-1，maxLen )； } } }返回ans； }； 716 ms 24.8 MB
2.3中心扩张法有2n 1个中心，两个字符之间有class solution { public : stringlongestpalindrome (strings ) if ) s.size )=1) return s； int i，j，len，len1，len2，n=s.size (，maxLen=0； 字符串ans； for(I=0； i n； I ) ) Len1=centerspand(s，I，I )； len2=centerspand(s，I，i 1)； len=max(len1，len2)； if(LenMaxlen ) ) { maxLen=len； ans=s.substr(I-(Len-1 )/2，len )； } }返回Ans； (intcenterspand(strings，int l，int r ) ) intlen=0； if(L==R ) len，L----，r； wile(l=0RS.size ) ) s ) l )=s(r ) ) { len =2； L----； r； }返回len； }； 60 ms 10.5 MB