leetcode刷题笔记-516.最长回文子序列

题目

https://leetcode.cn/problems/longest-palindromic-subsequence/

给你一个字符串 s ，找出其中最长的回文子序列，并返回该序列的长度。

子序列定义为：不改变剩余字符顺序的情况下，删除某些字符或者不删除任何字符形成的一个序列。

1
2
3
4
5
6
7
8
9
示例 1：
输入：s = "bbbab"
输出：4
解释：一个可能的最长回文子序列为 "bbbb" 。

示例 2：
输入：s = "cbbd"
输出：2
解释：一个可能的最长回文子序列为 "bb" 。

提示：

1
2
1 <= s.length <= 1000
s 仅由小写英文字母组成

思路1：最长公共子序列

这道题可以直接使用1143.最长公共子序列的代码，只要把原始字符串反转一下，就变成了两个字符串中求最长公共子序列的问题了。

对于回文子序列来说，字符串翻转过后也一定和原有的回文子序列相同，所以将原始字符串翻转后就能通过最长公共子序列找到最长的回文子序列。

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
32
class Solution {
    int longestCommonSubsequence(string a, string b) {
        int result = 0; // 结果集初始化
        // dp[i][j] 代表a中i和b中j下标和下标之前的最长公共子序列的长度
        // i为0和j为0的情况下，长度为0的字符串是不会有公共子序列的，所以可以全部初始化为0
        vector<vector<int>> dp(a.size() + 1, vector<int>(b.size() + 1, 0));
        // 判断 a[i-1] == b[j-1] 代表公共子序列可以扩展
        // dp[i][j] = dp[i-1][j-1] + 1
        // 其他情况，代表公共子序列不能扩展，那么当前的最长公共子序列和前一位的相同
        // 因为是二维数组，所以“前一位”其实有两种情况，分别是i-1和j-1，用max取最大值
        for (int i = 1; i <= a.size(); i++) {
            for (int j = 1; j <= b.size(); j++) {
                if (a[i - 1] == b[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
                }
                if (dp[i][j] > result) {
                    result = dp[i][j];
                }
            }
        }
        return result;
    }

public:
    int longestPalindromeSubseq(string s) {
        string b = s;
        reverse(b.begin(), b.end());
        return longestCommonSubsequence(s, b);
    }
};

整体的时间复杂度和空间复杂度都是O(N^2)。

image.png

思路2：动态规划

思路

有了用之前写过的题目的思路，下面还是得想一个直接写这道题的思路。总不能回避问题嘛。

因为回文的结构一般都是要从字符串中心开始向两次扩张来判断的，本题中只有一个字符串，所以不要和之前写的其他题目搞混了。

  • dp[i][j]代表字符串s中[i,j]范围内的最长回文子序列的长度。

因为单个字符也可以认为是回文子序列，所以当i等于j的时候，初始化为1。对于这个dp数组，我们只需要关注i<j的情况，所以i>j的位置都需要初始化为0。

这里可以沿用5.最长回文子串的思路，当i和j相等，回文子序列扩张的时候，最长的回文子序列的长度只能比[i+1,j-1]的范围多一对字符（即多两个字符）。

其他情况，因为本题求的是子序列，i和j不相等代表子序列不能被扩展，但dp数组的含义是[i,j]范围内的最长回文子序列的长度，所以当前的值依旧需要更新为“上一个结果”的值，对应本题也是在dp[i+1][j]和dp[i][j-1]中用max选最大值。对应的含义是把当前的s[i]或s[j]分别加入已有子序列中，看看谁可以组成更长的回文子序列。

这一点可以看下面这张借来的图，我们发现s[i]!=s[j]，但是把s[j]单独计入回文子序列会增加回文子序列的长度。正是因为我们的递推公式在之前已经遍历过这种情况计算出了一个最长回文子序列的结果，所以这里能直接沿用，且无需进行判断或给长度+1操作。

image.png

所以，递推代码如下：

1
2
3
4
5
if(s[i] == s[j]){
	dp[i][j] = dp[i+1][j-1]+2;
}else{
	dp[i][j] = max(dp[i+1][j],dp[i][j-1]);
}

根据这个递推方程，dp[i][j]的依赖项是dp[i+1][j-1]、dp[i+1][j]、dp[i][j-1]，对于一个矩阵而言，是它的左下角的部分，如下图所示。

image.png

根据依赖关系，我们遍历的时候，需要从i开始倒序遍历；因为依赖项中有j-1，所以j是正序遍历。

遍历顺序确定了，维护一个最大值，或者直接返回dp[0][s.size()-1]即为本题所求结果。

代码

完整代码如下。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    int longestPalindromeSubseq(string s) {
        int n = s.size();
        // dp[i][j]代表s中[i,j]范围内最长公共子序列的长度
        vector<vector<int>> dp(n, vector<int>(n, 0));
        // i和j相等的情况初始化为1
        for (int i = 0; i < n; i++) {
            dp[i][i] = 1;
        }
        // 开始递推
        for (int i = n - 1; i >= 0; i--) {
            // j 必须大于i
            for (int j = i + 1; j < n; j++) {
                if (s[i] == s[j]) {
                    dp[i][j] = dp[i + 1][j - 1] + 2;
                } else {
                    dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);
                }
            }
        }
        return dp[0][n - 1];
    }
};

image.png