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 问题
Initial state:
table[i][i] = true.
table[i][i+1] = (s[i]==s[i+1]);
State Change:
if s[i]==s[j], table[i][j]=table[i+1][j-1]
class Solution {
public:
string longestPalindrome(string s) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
int n = s.size();
if(n < ) return s;
vector<vector<bool>> table(n, vector<bool>(n,false));
//init length 1
for(int i = ; i< n; i++)
table[i][i] = true;
int len, maxlen = , maxStart = ,i,j;
for(len = ; len <= n ; len ++)
{
for(i = ; i< n - len + ; i++)
{
j = i + len - ;
if(s[i] == s[j] &&len == )
{
table[i][j] = true;
maxlen = len;
maxStart = i;
}
else if (s[i] == s[j] && table[i+][j-])
{
table[i][j] = true;
maxlen = len;
maxStart = i;
}
}
}
return s.substr(maxStart , maxlen);
}
};
这里解释下为什么len ==2 要单独处理： 因为table[i][j]只有上三角的值有意义，即 j >= i ; 当len = 2 时，table[i+1][j-1] j-1= i+2-1-1 = i 即此时j-1< i+1 ; 所以要单独处理
reference :http://leetcode.com/2011/11/longest-palindromic-substring-part-i.html
http://www.geeksforgeeks.org/dynamic-programming-set-12-longest-palindromic-subsequence/