5 最長回文子串

題目

給你一個字元串 s，找到 s 中最長的回文子串。

示例 1：

輸入：s = “babad”

輸出：“bab”

解釋：“aba” 同樣是符合題意的答案。

示例 2：

輸入：s = “cbbd”

輸出：“bb”

示例 3：

輸入：s = “a”

輸出：“a”

示例 4：

輸入：s = “ac”

輸出：“a”

• 方法一：中心擴散法

class Solution {
public:
    string longestPalindrome(string s) {
        if(s.size()<2) return s;
        int strLen = s.size();
        int right = 0, left = 0;//從目前節點到兩邊搜尋的左右指針
        int len = 1;//回文串的長度
        int maxLen = 0, maxStar = 0;//最長回文串的長度，最長回文串起始位置的前一個位置
        //對每一個節點向兩邊搜尋以它為中心的回文串
        for(int i=0; i<strLen; i++){
            left = i-1;
            right = i+1;
            //向左搜尋
            while(left>=0 && s[left]==s[i]){
                left--;
                len++;
            }
            //向右搜尋
            while(right<strLen && s[i]==s[right]){
                right++;
                len++;
            }
            //向兩邊搜尋
            while(left>=0 && right<strLen && s[left] == s[right]){
                left--;
                right++;
                len += 2;
            }
			//更新最長回文串的長度
            if(len>maxLen){
                maxLen = len;
                maxStar = left;
            }
            len = 1;//重新将len初始化為1
        }
        return s.substr(maxStar+1,maxLen);//傳回最長回文串
    }
};
           

• 時間複雜度O(n^2)
• 空間複雜度O(1)
• 思路
  • 中心擴散法，就是從每個位置出發，向兩邊擴散。先向左搜尋有沒有與目前位置相同的字元，如果有就繼續向左搜尋，直到下标越界或與目前位置字元不同。同理，再向右搜尋。兩邊搜尋結束後，左右指針所指的位置都是與目前位置元素不同的元素，此時同時向兩邊搜尋，如果左指針和右指針所指的元素相同，就繼續向兩邊搜尋，直到二者不同或下标越界。
  • 如果對該節點搜尋結束後回文串的長度len大于此前最長回文串的長度，則更新maxLen和maxStar。
  • 對字元串的全部節點搜尋結束時，left指的是回文串起始位置的前一個位置.
  • s.substr(start,len)第一個參數是子串的起始位置，為必選項，第二個參數是傳回子串的長度，是可選項，預設為到s的結尾。
• 方法二：動态規劃

class Solution {
public:
    string longestPalindrome(string s) {
        int n = s.size();
        int maxLen = 1, maxStart = 0;
        vector<vector<bool> > dp(n,vector<bool>(n));
        //按列周遊，從上往下，從左往右
        for(int r=1; r<n; r++){
            for(int l = 0; l<r; l++){
            	//如果目前的l和r相同
            	//且它們确定的區間有三個以内字元或它們确定的開區間内為回文串，則該閉區間為回文串
                if(s[l]==s[r] && (r-l<3 || dp[l+1][r-1])){
                    dp[l][r] = true;
                    //計算回文串長度
                    if(maxLen<r-l+1){
                        maxLen = r-l+1;
                        maxStart = l;
                    }
                }
            }
        }
        return s.substr(maxStart,maxLen);
    }
};
           

• 時間複雜度O(n^2)
• 空間複雜度O(n^2)
• 思路
  • 确定dp數組的下标及含義：dp[l][r]表示區間[l, r]是否為回文串，是則為true，否則為false
  • 确定遞推公式
    • 如果s[l]與s[r]不相等，則[l,r]必不是回文串，dp[l][r]為false
    • 如果s[l]與s[r]相等，則判斷它是否為回文串有三種情況
      • 如果l=r，即隻有一個字元的情況，它必然為回文串
      • 如果r-l =1,即隻有兩個字元的情況，此時二者相等，它必然為回文串
      • 如果r-l>1，即有三個或三個以上的字元。有三個字元時，由于兩側的兩個字元已經相當，則它必然也是回文串。多餘三個字元時，是否為回文串就要看除了兩側的兩個字元外的子串是否為回文串，即[l+1,r-1]是否為回文串。
  • dp數組的初始化：為true表示該區間為回文串，還沒判斷自然不可能知道是否為回文串，初始化為false
  • 确定周遊順序：dp[l+1][r-1]要在dp[l][r]之前确定。按列周遊，從上往下，從左往右；或者按行周遊，從左往右，從下往上。
• 方法三：Manacher 算法
• 時間複雜度O(n)
• 空間複雜度O(n)

中心擴散法詳解參考

動态規劃法詳解參考一

動态規劃法詳解參考二

Manacher 算法