【LeetCode】5. 最长回文子串

题目描述

给你一个字符串 s，找到 s 中最长的回文子串。

示例 1：

输入：s = “babad”
输出：“bab”
解释：“aba” 同样是符合题意的答案。

示例 2：

输入：s = “cbbd”
输出：“bb”

提示：

1 <= s.length <= 1000
s 仅由数字和英文字母组成

方法一：动态规划

class Solution {
public:
    string longestPalindrome(string s) {
        // dp数组表示坐标(i, j)上的回文长度
        vector<vector<int>> dp(s.length(), vector<int>(s.length(), 0));
        int maxLength=1; // 保存最长回文子串的长度
        int max_i=0; // 保存最长回文子串的左下标
        for(int i=s.length(); i>=0; i--){
            for(int j=i; j<s.length(); j++){
                if(s[i] == s[j]){
                    if(i+1 >= j) // 第一二种情况
                        dp[i][j] = j-i+1;
                    else if(dp[i+1][j-1]>0) // 第三种情况
                        dp[i][j] = dp[i+1][j-1] + 2;
                    
                    if(dp[i][j] > maxLength){ // 更新最长回文子串长度及下标
                        maxLength = dp[i][j];
                        max_i = i; 
                    }
                }
            }
        }
        return s.substr(max_i, maxLength);
    }
};
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

方法二：中心扩展法

class Solution {
public:
    int max_i=0, maxLength=1;
    string longestPalindrome(string s) {
        for(int i=0; i<s.length(); i++){
            extend(s, i, i, s.length());
            extend(s, i, i+1, s.length());
        }
        return s.substr(max_i, maxLength);
    }
    void extend(const string& s, int i, int j, int n){
        while(i>=0 && j<=n && s[i]==s[j]){
            i--;
            j++;
        }
        if(j-i-1 > maxLength){
            maxLength = j-i-1;
            max_i = i+1;
        }
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

心得

• 这道题是昨天题 [回文子串] 的进一步扩展，有了之前的基础就不算太难，还是延续昨天的两种方法动态规划和中心扩展法解决这个问题。
• 本题中心扩展法性能更佳。
• 方法一：动态规划法

• 思路在这里不再赘述，结尾会放上昨天的题解。主要就是对dp数组的定义做了修改，dp[i][j]用来存储回文子串的长度，保存当前最长的回文子串和下标，方便返回最终的结果。
• 踩雷的点：
  1.第一个for循环i>=0，一开始写成i>0，导致了一些错误，还是要细心一点；
  2.dp数组的计算时j-i+1，一开始写成j-i；
  3.字符串截取函数.substr不熟悉。
• 时间复杂度：O(n²)
• 空间复杂度：O(n²)

方法二：中心扩展法/双指针法

• 思路也是和昨天类似，不同的是昨天的extend函数只需要返回结果值，今天我的思路需要返回max_i和maxLength，索性直接把这两个变量变成全局变量。
• 时间复杂度：O(n²)
• 空间复杂度：O(1)

参考题解：
[1]【LeetCode】647. 回文子串