Longest Palindromic Substring

最长回文子序列

Description:Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

• 动态规划

状态转移方程 cpp class Solution { public: string longestPalindrome(string s) { if (s.empty()) return ""; int n = s.size(); int dp[n][n] = {0}; int left=0, right=0,len=0; for(int i=0; i<n;++i) { for(int j=0;j<i;++j) { dp[j][i] = (s[i] == s[j] && (i-j<2 || dp[j+1][i-1])); if(dp[j][i] && len <= i-j+1) { left = j; right=i; len=i-j+1; } } dp[i][i]=1; } return s.substr(left, right-left+1); } };