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"
大致意思：给定一个字符串s，从中找出最长的回文子串，要求字符串s最大长度为1000。
常规解法：首先针对字符串中的每一个字符，找到以该字符为中心的最长回文子串长度，记录下最长的字符串就可以了。这里需要注意回文子串长度有奇数和偶数两种情况：奇数情况以每一个字符为对称轴；偶数情况以两个字符中间的空字符为对称轴。遍历的时候分别通过一个字符(i,i)和两个字符(i,i+1)即可解决奇偶数问题。
class Solution {
public:
void getLen(string s,int m,int n,int &pos,int &len)
{
while(m>=0 && n<s.length() && s[m]==s[n])
{
--m;
++n;
}
if(n-m-1>len)
{
pos=m+1;
len=n-m-1;
}
}
string longestPalindrome(string s) {
int n=s.length();
int start=0;
int maxlen=1;
for(int i=0;i<n;++i)
{
getLen(s,i,i,start,maxlen);
getLen(s,i,i+1,start,maxlen);
}
return s.substr(start,maxlen);
}
};
其他解法：采用动态规划。先将整个问题分解为多个子问题，先想明白两个问题：（1）一个字符a是回文，两个字符aa也是回文；（2）如果一个字符串是回文，那么如果从该字符串向两边分别扩展一个字符得到一个新字符串，且扩展的这两个字符相同，那么这个新的字符串也是回文字符串。以此类推不断扩展，来求得最长回文字符串。其实这两个问题就是动态转移方程的推理过程：
Define P[ i, j ] ← true iff the substring Si … Sj is a palindrome, otherwise false.
P[ i, j ] ← ( P[ i+1, j-1 ] and Si = Sj ) ，显然，如果一个子串是回文串，并且如果从它的左右两侧分别向外扩展的一位也相等，那么这个子串就可以从左右两侧分别向外扩展一位。
其中的base case是
P[ i, i ] ← true
P[ i, i+1 ] ← ( Si = Si+1 )
之前看到有人画过一张图来辅助理解整个推理过程，如下图所示。
图示：对角线中（i，i）位置的1表明每一个字符都是回文字符串，（0，2）位置的1表明字符串“aba”是回文字符串。
class Solution {
public:
string longestPalindrome(string s) {
int n=s.length();
int start=0;
int maxlen=1;
bool isPalindrome[1000][1000]={false};
for(int i=0;i<n;++i)
{
isPalindrome[i][i]=true;
}
for(int j=0;j<n-1;++j)
{
if(s[j]==s[j+1])
{
isPalindrome[j][j+1]=true;
start=j;
maxlen=2;
}
}
for(int len=3;len<=n;++len)
{
for(int i=0;i<n-len+1;++i)
{
int j=i+len-1;
if(isPalindrome[i+1][j-1] && s[i]==s[j])
{
isPalindrome[i][j]=true;
start=i;
maxlen=len;
}
}
}
return s.substr(start,maxlen);
}
};
代码解释：因为一个字符比如“a”是回文，所以先将（i，i）位置全部置1，此时最长回文串长度为1；相邻字符如果相同比如"aa"则也是回文，将这样（i，i+1）的相邻位置也置1，此时最长回文串长度为2；剩下的从最长回文串长度为3的地方开始，如果一个字符两边分别扩展一个相同字符，则扩展后的新字符串仍然是回文字符串，如果两个相邻的回文串两边分别扩展一个相同的字符串，则扩展后的字符串也是回文串，此时最长回文串长度为4。以此类推，按照动态转移方程即可将最长回文子串求出，代码如上图所示。
