題目描述

給你一個(gè)字符串 s，找到 s 中最長(zhǎng)的回文子串。

示例 1：

輸入：s = "babad"
輸出："bab"
解釋："aba" 同樣是符合題意的答案。

示例 2：

輸入：s = "cbbd"
輸出："bb"

中心擴(kuò)散法

直接兩張圖就能夠解釋，如下是兩種情況：

• 第一種：
  由中間一個(gè)字符向左右兩邊進(jìn)行擴(kuò)散，當(dāng)左右兩端的字符相等時(shí)，繼續(xù)擴(kuò)散，否則停止，得到當(dāng)前最長(zhǎng)的回文子串。
  

  way1

• 第二種：
  由中間的2個(gè)字符向左右兩邊進(jìn)行擴(kuò)散，當(dāng)左右兩端的字符相等時(shí)，繼續(xù)擴(kuò)散，否則停止，得到當(dāng)前最長(zhǎng)的回文子串。
  

  way 2

C++實(shí)現(xiàn)：

// 中心擴(kuò)散法
class Solution {
public:
    string longestPalindrome(string s) {
        int n = s.length();
        if(n <= 1) return s;
        int begin = 0;
        int maxNum = 1;
        for(int i = 0;i < n-1;++i)
        {
            int tnum = 1;
            int ti = 1;
            while(i - ti >= 0 && i + ti < n && s[i-ti] == s[i+ti])
            {// 由中間的一個(gè)字符向兩邊擴(kuò)散
                tnum += 2;
                if(tnum > maxNum) {maxNum = tnum;begin = i-ti;}
                ti++;
            }
            
            ti = 0;
            tnum = 0;
            while(i - ti >= 0 && i + 1 + ti < n && s[i-ti] == s[i + 1 + ti])
            {// 由中間的兩個(gè)字符向兩邊擴(kuò)散
                tnum+=2;
                if(tnum > maxNum) {maxNum = tnum;begin = i-ti;}
                ti++;
            }
            
        }
        return s.substr(begin,maxNum);
    }
};

Go實(shí)現(xiàn):

// 中心擴(kuò)散法
func longestPalindrome(s string) string {
    n := len(s)
    if n <= 1 {
        return s
    }
    begin := 0
    maxNum := 1

    for i := 0; i < n; i++ {
        // 由中間的一個(gè)字符開始擴(kuò)散
        left := i - 1
        right := i + 1
        for left >= 0 && right < n && s[left] == s[right] {
            if right - left + 1 > maxNum {
                begin = left
                maxNum = right - left + 1
            }
            left--
            right++
        }
        // 由中間的2個(gè)字符開始擴(kuò)散
        left = i
        right = i + 1
        for left >= 0 && right < n && s[left] == s[right] {
            if right - left + 1 > maxNum {
                begin = left
                maxNum = right - left + 1
            }
            left--
            right++
        }
    }
    return s[begin:begin + maxNum]
}

動(dòng)態(tài)規(guī)劃

可以列一個(gè)表格，對(duì)于解決字符串相關(guān)的動(dòng)態(tài)規(guī)劃，最好是列一個(gè)表格進(jìn)行分析，這樣便于找出字符串之間的轉(zhuǎn)化規(guī)律。

下表中，X表示無用的單元格，1表示字符串s[j:i]是一個(gè)回文子串，0表示字符串s[j:i]不是一個(gè)回文子串。

遍歷的方向如下：

遍歷方向

C++實(shí)現(xiàn)

class Solution {
public:
    string longestPalindrome(string s) {
        // 動(dòng)態(tài)規(guī)劃的表格存儲(chǔ)的不是最長(zhǎng)回文長(zhǎng)度，而是子串是否是回文的標(biāo)志
        int n = s.length();
        if(n < 2) return s;
        vector<vector<bool>> dp(n,vector<bool>(n,true));
        int maxi = 0,maxj = 1,maxLen = 1;
        for(int j = 1;j < n;++j)
        {
            for(int i = 0;i < j;++i)
            {
                if(s[i] != s[j])
                    dp[i][j] = false;
                else{
                    if(j - i < 3) dp[i][j] = true;
                    else dp[i][j] = dp[i+1][j-1];
                }
                if(dp[i][j])
                {
                    if(j - i + 1 > maxLen)
                    {
                        maxLen = j - i + 1;
                        maxi = i;
                        maxj = j;
                    }
                }
            }
        }
        return s.substr(maxi,maxLen);
    }
};

Go實(shí)現(xiàn)

// 動(dòng)態(tài)規(guī)劃
func longestPalindrome(s string) string {
    n := len(s)
    if n <= 1 {
        return s
    }
    begin := 0
    maxNum := 1
    // == 創(chuàng)建二維動(dòng)態(tài)數(shù)組并且初始化 ==
    table := make([][]bool,n)
    for i := 0; i < n; i++ {
        table[i] = make([]bool,n)
    }
    for i := 0; i < n; i++ {
        table[i][i] = true
    }
    // ============================

    // 動(dòng)態(tài)規(guī)劃進(jìn)行迭代計(jì)算
    for i := 1; i < n; i++ {
        for j := i-1; j >= 0; j-- {
            if s[i] != s[j] {
                table[j][i] = false
            } else {
                if i - j >= 2 {
                    table[j][i] = table[j+1][i-1]
                } else {
                    table[j][i] = true
                }
            }
            if table[j][i] && i - j + 1 > maxNum {
                maxNum = i - j + 1
                begin = j
            }
        }
    }
    return s[begin:begin+maxNum]
}

參考

• 5. 最長(zhǎng)回文子串