[LeetCode] Longest Palindromic Substring

Given a string S, find the longest palindromic substring in S. You may assume that the maximum length of S is 1000, and there exists one unique longest palindromic substring.

思路：

一开始觉得是一维DP。dp[i]记录以i为结尾的最长回文的长度，然后有通项公式：

dp[i] = dp[i-1] + 2，如果s[i] = s[j]，j = i - dp[i-1] - 1。否则为dp[i] = 1

例如：a b c b a d
p[3] = 3 && s[4] = s[0] => dp[4] = 5

但是仔细一想，当s[i] != s[j]时，dp[i]实际是无法确定的。

例如：b a c c a c
dp[4] = 4 (a c c a)，但s[5] != s[0]，而实际dp[5] = 3因为s[5] = s[3]，且s[4:4]是回文。

因此这题不是简单的一维DP，而是二维DP，需要计算并记录任意s[i:j]是否是回文：

定义bool isPal[i][j]表示s[i:j]是否为回文，isPal[i][j] = true需要满足两个条件: 
1. s[i] ==s[j]
2. i+1>j-1或 isPal[i+1][j-1] == true (即s[i+1 : j-1]是回文)

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22

class Solution { public: string longestPalindrome(string s) { if(s.size()<=1) return s; int start = 0, maxLen = 1, n = s.size(); bool isPal[1000][1000] = {false}; for(int i=n-1; i>=0; i--) { for(int j=i; j<n; j++) { if((i+1>j-1 || isPal[i+1][j-1]) && s[i]==s[j]) { isPal[i][j] = true; if(j-i+1>maxLen) { maxLen = j-i+1; start = i; } } } } return s.substr(start,maxLen); } };