5. 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.

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。以此类推，按照动态转移方程即可将最长回文子串求出，代码如上图所示。