classSolution { public: string longestPalindrome(string s){ if(s.length() < 2) return s; int maxLen = 1; int left = 0; for(int i = 0; i < s.length() - 1; i ++) { int len1 = centerExpand(s, i, i); int len2 = centerExpand(s, i, i + 1); int maxn = max(len1, len2); if(maxn > maxLen) { maxLen = maxn; left = i - (maxLen - 1) / 2; } } return s.substr(left, maxLen); } intcenterExpand(string s, int left, int right){ while(left >= 0and right < s.length() and s[left] == s[right]) { left --; right ++; } return right - left - 1; } };
DP
There is a regular pattern: if the string s is a palindromic string, then after removing the head and tail character, the rest string is still a palindromic string.
We use dp[i][j] to represents if the the substring s[i, j] a palindromic string.
So, dp[i][j] is based on s[i] == s[j] && dp[i+1][j-1]
And the i+1 , j-1 must be form a legal string, so j-1 - (i+1) >= 2 => j - i >= 3
First, the diagonal means the character itself, so it should be true;
0
1
2
3
4
0
true
1
true
2
true
3
true
4
true
So we can just fill the form, fill them by column, and in each column fill in ascending order. ( babab )