3種解法 - 求解最長回文子串

文章目錄

• • 題目
  • 解法一（暴力法）
  • 解法二（中心擴充）
  • 解法三（動态規劃）

題目

給定一個字元串 s，找到 s 中最長的回文子串。你可以假設 s 的最大長度為 1000。

示例 1：

輸入: “babad”

輸出: “bab”

注意: “aba” 也是一個有效答案。

示例 2：

輸入: “cbbd”

輸出: “bb”

解法一（暴力法）

思路：原理就是對字元串從前到後依次進行周遊，最外層循環為子串頭，第二層循環為确定子串尾，第三層循環為确定子串是否滿足回文限制。

1. 确定子串頭i，子串尾j
2. 判斷子串是否滿足回文，并記錄最長回文子串

• 時間複雜度：O(n3)

• 空間複雜度：O(1)

  目前方案的時間複雜度太高，對于比較長的字元串會執行逾時，尤其是字元串内容完全相同的情況，逾時測試用例（1000個z）及源碼如下：

  https://www.zhenxiangsimple.com/files/tech/testCase20200206.txt

public class Solution {
    public string LongestPalindrome(string s) {
        int idx = 0,len = -1;
        bool flag = false;
        for(int i=0;i<s.Length;i++)
        {//從前往後周遊，确定起始字元
            for(int j=s.Length-1;j>=i;j--)
            {//從後往前周遊，确定結束字元
                if(s[i] != s[j]) continue;
                flag = false;
                for(int m=i,n=j;m<n;m++,n--)
                {//檢查中間部分是否為回文子串
                    if(s[m] != s[n]) 
                    {
                        flag = true;
                        break;
                    }
                }
                if(!flag && j-i > len)
                {//記錄最長子串
                    len = j - i;
                    idx = i;
                }
            }
        }
        return len > -1?s.Substring(idx,len+1):"";
    }
}
           

解法二（中心擴充）

思路：把每個字元作為回文串的中心點，向兩邊擴充進行檢測來确定目前字元為中心的回文串長度，所有子串的最大長度即為所求。

1. 以字元為中心位置進行檢測是否滿足回文串
2. 對所有字元進行周遊
3. 當子串為偶數和奇數時對應的順序不一緻，本解法種分别對每個字元驗證偶數和奇數兩種情況，并保留最長串

• 時間複雜度：O(n2)
• 空間複雜度：O(1)

public class Solution {

    public void CheckWord(string s,int m,int n,out int idx,out int len)
    {
        for(;m>=0 && n<s.Length;m--,n++)
        {
            if(s[m] != s[n]) 
            {
                break;
            } 
        }
        //需要回溯一個位置
        m++;
        n--;
        len = n - m;
        idx = m;        
    }

    public string LongestPalindrome(string s) {
        int idx = 0,len = -1;
        int tmpIdx,tmpLen;
        for(int i=0;i<s.Length;i++)
        {
        	//奇數，即有一個字元在中間位置
            CheckWord(s,i-1,i+1,out tmpIdx,out tmpLen);
            if(tmpLen > len)
            {
                idx = tmpIdx;
                len = tmpLen;
            }
            //偶數，即中間是兩個相同的字元，或沒有一個具體字元在中間
            CheckWord(s,i,i+1,out tmpIdx,out tmpLen);
            if(tmpLen > len)
            {
                idx = tmpIdx;
                len = tmpLen;
            }
        }
        return len > -1?s.Substring(idx,len+1):"";
    }
}
           

解法三（動态規劃）

思路：可以當做基于暴力解法的一種優化，将已經得到的回文串儲存起來，用于求解新的回文串。對于一個回文子串，如果兩邊的字母一樣，則可以分别向兩邊擴充一步形成新的回文串，如果兩邊字母不同，那目前串即為最長回文子串，直到找到最長的字元。

1. 1個和2個字元屬于特殊情況需要特殊處理，1個字元都是回文串，2個字元如果相等就是回文串，如果不等就不是。
2. 利用遞推公式：如果 s [ i + 1 , j − 1 ] s[i+1,j-1] s[i+1,j−1]是回文，且 s [ i ] = = s [ j ] s[i]==s[j] s[i]==s[j]，那麼 s [ i , j ] s[i,j] s[i,j]也是回文串
3. 使用一個二維數組儲存之前記錄的回文串，數組橫縱下标分别表示字元的起止索引是否為回文串，即t[i,j]=true表示s[i…j]是回文串

• 時間複雜度：O(n2)
• 空間複雜度：O(n2)

public class Solution {
    public string LongestPalindrome(string s) {
        bool [,] t = new bool[s.Length,s.Length];
        int len=-1,idx=0, j;
        for(int l=0;l<s.Length;l++)
        {//子串前後間隔長度
            for(int i=0;i<s.Length-l;i++)
            {//子串起始位置
                j = i+l;//結束位置
                if(s[i] == s[j] && (l<=2 || t[i+1,j-1]))
                {
                    t[i,j] = true;
                    if(l > len)
                    {
                        len = l;
                        idx = i;
                    }
                }
            }
        }
        return len > -1?s.Substring(idx,len+1):"";
    }
}