# Leetcode 5 Longest Palindromic Substring DP(Leetcode 5 Longest Palindromic Substring DP)-其他

## Leetcode 5 Longest Palindromic Substring DP(Leetcode 5 Longest Palindromic Substring DP)

Given a string , return the longest palindromic substring in .

``s``
``s``

### Solution

``````class Solution {
private:
bool dp[1003][1003];
int MAX = -1;
int ansl, ansr;

public:
string longestPalindrome(string s) {
int n = s.length();
for(int i=0;i<n;i++){
dp[i][i] = true;
MAX = 1; ansl = i;
}
for(int j=1;j<n;j++){
for(int i=j-1;i>=0;i--){
if(i+1==j){
if(s[i]==s[j])dp[i][j] = true;
else dp[i][j] = false;
}
else{
if(s[i]==s[j] && dp[i+1][j-1])dp[i][j] = true;
else dp[i][j] = false;
}
if(dp[i][j]){
if(MAX<j-i+1)MAX = j-i+1, ansl = i, ansr = j;
}
}
}
return s.substr(ansl, MAX);
}
};
``````
————————

Given a string , return the longest palindromic substring in .

``s``
``s``

### Solution

Set \ (DP [i] [J] \) to indicate whether the string \ (s [I,…, J] \) is a palindrome string. During initialization, each individual character itself is a palindrome string; A string with a length of 2 is also a palindrome string as long as the beginning and end are the same; When the length is \ (\ GEQ 3 \), only:

At this time \ (dp[i][j]\) is the palindrome string. Therefore, when \ (I \) inside the loop, it should be traversed in reverse order

``````class Solution {
private:
bool dp[1003][1003];
int MAX = -1;
int ansl, ansr;

public:
string longestPalindrome(string s) {
int n = s.length();
for(int i=0;i<n;i++){
dp[i][i] = true;
MAX = 1; ansl = i;
}
for(int j=1;j<n;j++){
for(int i=j-1;i>=0;i--){
if(i+1==j){
if(s[i]==s[j])dp[i][j] = true;
else dp[i][j] = false;
}
else{
if(s[i]==s[j] && dp[i+1][j-1])dp[i][j] = true;
else dp[i][j] = false;
}
if(dp[i][j]){
if(MAX<j-i+1)MAX = j-i+1, ansl = i, ansr = j;
}
}
}
return s.substr(ansl, MAX);
}
};
``````