LeetCode 5. 最长回文子串

• 1.动态规划
• 2.中心扩展法
• 3.中心扩展法的优化

题目链接：https://leetcode-cn.com/problems/longest-palindromic-substring/

思路如下：

假设字符串 s = “babad”，它的长度为 n。

dp 是大小为 n ∗ n n*n n∗n 的二维数组， d p [ i ] [ j ] dp[i][j] dp[i][j] 表示 s [ i , j ] s[i,j] s[i,j] 是否为回文串，存储 true/false。

如果 s [ i , j ] s[i,j] s[i,j] 的长度小于等于 2 2 2 时

• 如果 s [ i ] s[i] s[i] 等于 s [ j ] s[j] s[j]，那么 s [ i , j ] s[i,j] s[i,j] 是回文串，所以 d p [ i ] [ j ] = ( s [ i ] = = s [ j ] ) dp[i][j] = (s[i] == s[j]) dp[i][j]=(s[i]==s[j])

如果 s [ i , j ] s[i,j] s[i,j] 的长度大于 2 2 2 时

• 如果 s [ i + 1 , j − 1 ] s[i+1,j-1] s[i+1,j−1] 是回文串，并且 s [ i ] s[i] s[i] 等于 s [ j ] s[j] s[j]，那么 s [ i , j ] s[i,j] s[i,j] 是回文串
  所以 d p [ i ] [ j ] = d p [ i + 1 , j − 1 ]   & &   ( s [ i ] = = s [ j ] ) dp[i][j] = dp[i+1,j-1] && (s[i] == s[j]) dp[i][j]=dp[i+1,j−1] && (s[i]==s[j])

时间复杂度为 O ( n 2 ) O(n^2) O(n2)

空间复杂度为 O ( n 2 ) O(n^2) O(n2)

C++代码如下：

class Solution {
public:
    string longestPalindrome(string s) {
        int n = s.length();
        if (n == 0 || n == 1)   return s;

        vector> dp(n, vector(n));
        int maxLen = 1; // 记录最长回文子串的长度
        int beginIdx = 0; // 记录最长回文子串的开始索引

        for (int i = n - 1; i >= 0; i--) {
            for (int j = i; j < n; j++) {
                int len = j - i + 1;
                dp[i][j] = (s[i] == s[j]) && (len <= 2 || dp[i + 1][j - 1]);
                if (dp[i][j] && len > maxLen) {
                    maxLen = len;
                    beginIdx = i;
                }
            }
        }

        return s.substr(beginIdx, maxLen);
    }
};

思路如下：

枚举回文子串的中点，从中间向两边扩展，直到左右两边的字符不相等为止，记录最长的回文子串即可。

要注意区分长度为奇数的回文串和长度为偶数的回文串。

假设字符串 s = “abbaba” 的长度为 n n n，那么一共有 n + ( n − 1 ) = 2 n − 1 n+(n-1)=2n-1 n+(n−1)=2n−1个扩展中心。

时间复杂度为 O ( n 2 ) O(n^2) O(n2)

空间复杂度为 O ( 1 ) O(1) O(1)

C++代码如下：

class Solution {
public:
    string longestPalindrome(string s) {
        int n = s.length();
        if (n == 0 || n == 1)   return s;

        int maxLen = 1; // 记录最长回文子串的长度
        int beginIdx = 0; // 记录最长回文子串的开始索引

        for (int i = 0; i < n; i++) {
        	// 以字符s[i]为中心，向左、向右扩展
            int l = i - 1, r = i + 1;
            while (l >= 0 && r < n && s[l] == s[r]) {
                l--;
                r++;
            }
            if (r - l - 1 > maxLen) {
                maxLen = r - l - 1;
                beginIdx = l + 1;
            }
            
            // 以字符s[i]右边的间隙为中心，向左、向右扩展
            l = i, r = i + 1;
            while (l >= 0 && r < n && s[l] == s[r]) {
                l--;
                r++;
            }
            if (r - l - 1 > maxLen) {
                maxLen = r - l - 1;
                beginIdx = l + 1;
            }
        }
        
        return s.substr(beginIdx, maxLen);
    }
};

思路如下：

将连续的相同字符组成的子串作为扩展中心，所以字符串 s = “babbbabaa” 的扩展中心有 “b”、“a”、“bbb”、“a”、“b”、“aa”。

步骤：

• 找到右边第一个不等于 s [ i ] s[i] s[i] 的字符记为位置 r r r， s [ i ] s[i] s[i] 左边的位置记为 l l l
• r r r 作为下一次的 i i i
• 由 l l l 开始向左、 r r r 开始向右扩展，找到最长的回文子串

时间复杂度为 O ( n 2 ) O(n^2) O(n2)

空间复杂度为 O ( 1 ) O(1) O(1)

C++代码如下：

class Solution {
public:
    string longestPalindrome(string s) {
        int n = s.length();
        if (n == 0 || n == 1)   return s;

        int maxLen = 1; // 记录最长回文子串的长度
        int beginIdx = 0; // 记录最长回文子串的开始索引

        int i = 0;
        while (i < n) {
        	// s[i]左边的位置记为l
            int l = i - 1;

            // 找到右边第一个不等于s[i]的位置r
            int r = i + 1;
            while (r < n && s[r] == s[i]) {
                r++;
            }

            // r会成为新的i
            i = r;

            // 从l向左扩展，从r向右扩展
            while (l >= 0 && r < n && s[l] == s[r]) {
                l--;
                r++;
            }

            // 扩展结束后，s[l + 1, r - 1]就是刚才找到的最大回文子串
            if (r - l - 1 > maxLen) {
                maxLen = r - l - 1;
                beginIdx = l + 1;
            }
        }

        return s.substr(beginIdx, maxLen);
    }
};