最長回文子串

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。

常規(guī)解法：首先針對字符串中的每一個字符，找到以該字符為中心的最長回文子串長度，記錄下最長的字符串就可以了。這里需要注意回文子串長度有奇數(shù)和偶數(shù)兩種情況：奇數(shù)情況以每一個字符為對稱軸；偶數(shù)情況以兩個字符中間的空字符為對稱軸。遍歷的時候分別通過一個字符(i,i)和兩個字符(i,i+1)即可解決奇偶數(shù)問題。

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);
        
    }
};

其他解法：采用動態(tài)規(guī)劃。先將整個問題分解為多個子問題，先想明白兩個問題：（1）一個字符a是回文，兩個字符aa也是回文；（2）如果一個字符串是回文，那么如果從該字符串向兩邊分別擴(kuò)展一個字符得到一個新字符串，且擴(kuò)展的這兩個字符相同，那么這個新的字符串也是回文字符串。以此類推不斷擴(kuò)展，來求得最長回文字符串。其實這兩個問題就是動態(tài)轉(zhuǎn)移方程的推理過程：

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 ) ，顯然，如果一個子串是回文串，并且如果從它的左右兩側(cè)分別向外擴(kuò)展的一位也相等，那么這個子串就可以從左右兩側(cè)分別向外擴(kuò)展一位。

其中的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的地方開始，如果一個字符兩邊分別擴(kuò)展一個相同字符，則擴(kuò)展后的新字符串仍然是回文字符串，如果兩個相鄰的回文串兩邊分別擴(kuò)展一個相同的字符串，則擴(kuò)展后的字符串也是回文串，此時最長回文串長度為4。以此類推，按照動態(tài)轉(zhuǎn)移方程即可將最長回文子串求出，代碼如上圖所示。