5 最长回文子串

本文最后更新于：2021年3月7日 晚上

给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

示例 1：

1
2
3
输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。

示例 2：

1
2
输入: "cbbd"
输出: "bb"

Solution

动态规划方法同 [516 最长回文子序列](516 最长回文子序列.md)

  • 参考liweiwei1419 的题解

状态转移方程：

1
dp[i][j] = (s[i] == s[j]) and dp[i + 1][j - 1]

说明：

「动态规划」事实上是在填一张二维表格，由于构成子串，因此 i 和 j 的关系是 i <= j ，因此，只需要填这张表格对角线以上的部分。

看到 dp[i + 1] [j - 1] 就得考虑边界情况。

边界条件是：表达式 [i + 1, j - 1] 不构成区间，即长度严格小于 2，即 j - 1 - (i + 1) + 1 < 2 ，整理得 j - i < 3。

  • 如果子串 s[i + 1..j - 1] 只有 1 个字符，即去掉两头，剩下中间部分只有 1 个字符，显然是回文；
  • 如果子串 s[i + 1..j - 1] 为空串，那么子串 s[i, j] 一定是回文子串。
  • 因此，在 s[i] == s[j] 成立和 j - i < 3 的前提下，直接可以下结论，dp[i] [j] = true，否则才执行状态转移。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
# @lc code=start
class Solution:
    def longestPalindrome(self, s: str) -> str:
        n=len(s)
        dp=[[0 for _ in range(n)] for _ in range(n)]
        for i in range(n):
            dp[i][i]=1
        
        max_len = 1
        start=0
        for i in range(n-1, -1, -1):
            for j in range(i+1, n):
                if s[i]==s[j]:
                    if j-i<3:
                        dp[i][j]=1
                    else:
                        dp[i][j]=dp[i+1][j-1]
                else:
                    dp[i][j]=0
                
                if dp[i][j]:
                    cur_len=j-i+1
                    if cur_len>max_len:
                        max_len=cur_len
                        start = i
        return s[start:start+max_len]
# @lc code=end

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
public:
    string longestPalindrome(string s) {
        int n = s.size();
        // dp[i][j] 表示 s[i:j] 是否为回文子串
        vector<vector<bool>> dp(n, vector<bool>(n, false));
        for (int i = 0; i < n; ++i)
            dp[i][i] = true;
        
        int maxLen = 1, start = 0;
        for (int j = 1; j < n; ++j) {
            for (int i = 0; i < j; ++i) {
                if (s[i] == s[j]) {
                    if (j - i < 3)
                        dp[i][j] = true;
                    else 
                        dp[i][j] = dp[i+1][j-1];
                }
                else {
                    dp[i][j] = false;
                }

                if (dp[i][j] == true && (j-i+1 > maxLen)) {
                    maxLen = j - i + 1;
                    start = i;
                }
            }
        }
        return s.substr(start, maxLen);
    }
};
  • 中心扩散法，参考官方题解、《算法小抄》5.6
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def longestPalindrome(self, s: str) -> str:
        start, end = 0,0
        def palindrome(s, l, r):
            while l>=0 and r<len(s) and s[l]==s[r]:
                l-=1
                r+=1
            return l+1, r-1
        
        for i in range(len(s)):
            # 找到以 s[i] 为中心的回文串
            l1, r1=palindrome(s, i, i)
            # 找到以 s[i] 和 s[i+1] 为中心的回文串
            l2, r2=palindrome(s, i, i+1)
            if (r1-l1)>(end-start):
                start, end = l1, r1
            if (r2-l2)>(end-start):
                start, end = l2, r2
        return s[start:end+1]

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public:
    string longestPalindrome(string s) {
        int start = 0, end = 0;
        for (int i = 0; i < s.size(); ++i) {
            auto [l1, r1] = palindrome(s, i, i); // 单中心
            auto [l2, r2] = palindrome(s, i, i+1); // 双中心
            if (r1 - l1 > end - start) {
                start = l1;
                end = r1;
            }
            if (r2 - l2 > end - start) {
                start = l2;
                end = r2;
            }
        }
        return s.substr(start, end - start + 1);
    }

    // 中心扩散法
    pair<int, int> palindrome(const string& s, int l, int r) {
        while (l >= 0 && r < s.size() && s[l] == s[r]) {
            --l;
            ++r;
        }
        return {l+1, r-1};
    }
};