Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.
Example:
Input: “babad”
Output: “bab”
Note: “aba” is also a valid answer. Example:
Input: “cbbd”
Output: “bb”
思路：动态规划，复杂度O(n^2)。设状态为f(i,j),表示区间[i,j]是否为回文串，则状态转移方程为
class Solution { public: string longestPalindrome(string s) { int start=0,result=1; int n=s.size(); int dp[n][n]; for(int i=0;i<n;i++) for(int j=0;j<n;j++) dp[i][j]=0; for(int i=0;i<n;i++) dp[i][i]=1; for(int i=0;i<n;i++) for(int j=0;j<i;j++) { dp[j][i]=(s[j]==s[i]&&(i-j<2||dp[j+1][i-1])); if(dp[j][i]&&result<(i-j+1)) { start=j; result=i-j+1; } } return s.substr(start,result); } };