刷題筆記-最長回文子串

題目描述

https://leetcode-cn.com/problems/longest-palindromic-substring/

思路

利用動态規劃。

目前狀态為 dp[i][j]，表示字元串第 i 個字元和第 j 個字元之間是否是回文串（i<=j）。目前狀态與前一個狀态 dp[i+1][j-1] 有關，如果 dp[i+1][j-1] 是回文串，且 s[i]==s[j] ，則 dp[i][j] 也是回文串。

初始條件如下：單個字元一定是回文串，兩個相鄰字元如果相等，也能構成回文串。然後多次周遊字元串，第一次周遊先得到所有長度為3的字元串是否是回文串，再根據短字元串判斷稍長的字元串是否是回文串。

如果字元串長度為Max，那麼dp數組的大小應該設定為Max行Max列。但dp數組有一半的空間沒有用，因為i>j是無意義的。

本題中利用的是二維數組存放回文串頭尾index，空間複雜度是 O(n^2)。

實作

class Solution {
public:
    string longestPalindrome(string s) {
        int Max = s.length();
        if(Max==0)
            return "";
        bool dp[Max][Max];
        memset(dp,false,sizeof(dp));//
        int longest = 1, posl=0;
        for(int i=0; i<Max; i++)
            dp[i][i]=true;//單個字元組成的字元串一定是回文串
        for(int i=0; i<Max-1; i++)
            if(s[i]==s[i+1])
            {
                dp[i][i+1]=true;//相鄰字元相等
                longest = 2;
                posl = i;
            }
        for(int n=3; n<=Max; n++)
        {
            for(int i=0, j=i+n-1; j<Max; i++,j++)
            {
                if(dp[i+1][j-1] && s[i]==s[j])
                {
                    dp[i][j]=true;
                    longest = n;
                    posl = i;
                }
            }
        }
        string res(s,posl,longest);
        return res;
    }
};
           

動态規劃的dp數組一般情況下都是可以簡化的，也就是說duck不必記錄那麼多資料，有些資料用過一次就不會再用，可以直接被後來的資料覆寫掉。

本題中，要判斷長度為 L 的字元串是否是回文串時，就需要知道長度為 (L-2) 字元串是否是回文串，而對于長度為 (L+1) 的字元串，則需要知道 (L-1) 字元串的資訊。是以我們隻需要保留 2 行dp數組，用于記錄前一次和前前次周遊生成的資訊。這樣，空間複雜度可以降低為 O(n) 。

class Solution {
public:
    string longestPalindrome(string s) {
        int Max = s.length();
        if(Max==0)
            return "";
        if(Max==1)
            return s;
        bool dp[2][Max];
        memset(dp,true,sizeof(dp)/2);//單個字元一定是回文的
        memset(dp+1,false,sizeof(dp)/2);//相鄰字元不一定
        int longest = 1, posl=0;
        for(int i=0; i<Max-1; i++)
            if(s[i]==s[i+1])
            {
                dp[1][i]=true;//如果相鄰字元相等
                longest = 2;
                posl = i;
            }
        for(int n=3; n<=Max; n++)
        {
            for(int i=0, j=i+n-1; j<Max; i++,j++)
            {
                if(dp[(n-1)%2][i+1] && s[i]==s[j])
                {
                    dp[(n-1)%2][i]=true;
                    longest = n;
                    posl = i;
                    continue;
                }
                dp[(n-1)%2][i]=false;
            }
        }
        string res(s,posl,longest);
        return res;
    }
};
           

如果長度為 L-2 的所有字元串都不是回文串，那麼 L 的字元串就不可能是回文串。利用這個資訊，可以減小算法的平均時間複雜度。但算法的時間複雜度不變，仍為 O(n^2) 。

class Solution {
public:
    string longestPalindrome(string s) {
        int Max = s.length();
        if(Max==0)
            return "";
        if(Max==1)
            return s;
        bool dp[2][Max];
        memset(dp,true,sizeof(dp)/2);//單個字元一定是回文的
        memset(dp+1,false,sizeof(dp)/2);//相鄰字元不一定
        int longest = 1, posl=0;
        for(int i=0; i<Max-1; i++)
            if(s[i]==s[i+1])
            {
                dp[1][i]=true;//如果相鄰字元不相等
                longest = 2;
                posl = i;
            }
        //allfalse用來判斷長度為n的字元串是否都不是回文串，如果為真，就不用再判斷長度為n+2的字元串了。
        //isbreak用來控制目前循環提前結束。
        bool allfalse[2]={true,true}, isbreak[2]={false,false};
        for(int n=3; n<=Max; n++)
        {
            if(isbreak[0] && isbreak[1])
                break;
            if(isbreak[(n-1)%2])
                continue;
            for(int i=0, j=i+n-1; j<Max; i++,j++)
            {
                if(dp[(n-1)%2][i+1] && s[i]==s[j])
                {
                    allfalse[(n-1)%2]=false;
                    dp[(n-1)%2][i]=true;
                    longest = n;
                    posl = i;
                    continue;
                }
                dp[(n-1)%2][i]=false;
            }
            if(!allfalse[(n-1)%2]) allfalse[(n-1)%2]=true;
            else isbreak[(n-1)%2] = true;
        }
        string res(s,posl,longest);
        return res;
    }
};
           

其他算法

Manacher’s Algorithm，見解法5，時間複雜度可以降低到O(n)。

中心擴充算法，見解法4，時間複雜度O(n^2)，是動态規劃外的另外一種思路。