当前位置 : 主页 > 编程语言 > java >

leetcode 5. 最长回文子串

来源:互联网 收集:自由互联 发布时间:2022-07-13
leetcode [​​5. 最长回文子串​​](https://leetcode-cn.com/problems/median-of-two-sorted-arrays/) 给你一个字符串 ​​s​​​,找到 ​​s​​ 中最长的回文子串。 动态规划法求解最大回文串。 cl


leetcode [​​5. 最长回文子串​​](https://leetcode-cn.com/problems/median-of-two-sorted-arrays/)

给你一个字符串 ​​s​​​,找到 ​​s​​ 中最长的回文子串。

leetcode 5. 最长回文子串_状态方程

动态规划法求解最大回文串。

class Solution {
public:
string longestPalindrome(string s) {
bool dp[1005][1005]; //存储状态
int len = s.length(),ans = 1,from = 0;
for(int i = 0;i < len;++i) //状态初始化
dp[i][i] = true;
for(int i = 0,j = len - 1;i < j;++i)
if(s[i] == s[i + 1])
dp[i][i + 1] = true,ans = 2,from = i;
else
dp[i][i + 1] = false;
for(int i = 2,j = len;i < j;++i) //状态方程
for(int p = 0,q = len - i;p < q;++p)
if(s[p] == s[p + i]){
if(dp[p + 1][p + i - 1])
dp[p][p + i] = true,ans = i + 1,from = p;
else
dp[p][p + i] = false;
}
else
dp[p][p + i] = false;
return s.substr(from,ans);
}
};


上一篇:Java自学|异常
下一篇:没有了
网友评论