代码随想录 | Day 57 - LeetCode 647. 回文子串、516. 最长回文子序列

        今天是回文串问题，之前做过但忘记了，看到提示才做出来。这个问题需要首先想清楚dp矩阵定义为bool还是int类型，再理解“当前串是否为回文串依赖于去掉头尾的子串是否为回文串以及头尾相等关系”和“当前序列的最大回文子序列长度依赖于去掉头尾的子序列的最大回文子序列长度以及头尾相等关系”。依赖关系上，与之前的不同在于dp值依赖于其左下角了，所以遍历方向上要做相应的调整。

        第1题（LeetCode 647. 回文子串）没有思路，看了题解的dp定义后想起来之前做过，才做出来了。dp设置为bool类型，dp[i][j]（i ≥ j）定义为“s[i : j]是否为回文子串”。这样一来，dp矩阵包含了所有可能的子串，最后统计dp为true的数量作为答案就可以。对于dp[i][j]，分3种情况：

1. i与j相等，即s[i : j]就是一个字符。因为一个字符一定是回文串，所以dp[i][j]为true；
2. j等于(i + 1)，即s[i : j]是两个字符。那么dp[i][j]的取值就取决于s[i]与s[j]是否相等；
3. 其他情况下，只有“s[i + 1 : j - 1]是回文串，且s[i]与s[j]相等”时s[i : j]才是回文串。

        前两种情况的dp取值都不依赖于其他dp值，而第3种情况的dp[i][j]则依赖于dp[i + 1][j - 1]，也就是其左下角位置。另外由于i ≥ j，所以只需要填充dp矩阵的右上半部分（包括对角线）。所以需要初始化dp矩阵的对角线（对应情况1）以及对角线上每个值右边的第1个位置（对应情况2），这样才能保证在情况3下，每个位置的左下角被填充。

        同样因为这样的依赖关系，遍历方向上需要在外层循环由下至上，内层循环，由左到右，每一行都从对角线位置开始。对于每一行，最先被填充的是情况1，然后是情况2，之后是情况3。所以情况1和情况2不用提前初始化，在遍历过程中初始化即可。

class Solution {
public:
    int countSubstrings(string s) {
        vectorbool>> dp(s.size(), vector<bool>(s.size(), false));
        int ans = 0;
        for (int i = s.size() - 1; i >= 0; --i) {
            for (int j = i; j < s.size(); ++j) {
                if (j == i || j == i + 1 && s[j] == s[i] || dp[i + 1][j - 1] && s[i] == s[j]) {
                    ans++;
                    dp[i][j] = true;
                }
            }
        }
        return ans;
    }
};

        在实现上，可以像上面的代码一样，将dp矩阵全部初始化为false。然后针对三种情况进行判断，对于满足要求的点改为true，并进行计数。

        这道题还有空间复杂度为O(1)的双指针解法。左、右指针分别对应当前字符串的左、右两端。方法是让当前字符串的左、右指针分别左、右移，也就是对当前字符串扩展。如果移动后对应的两个新字符相等的话，就得到一个新的回文串。不相等的话就停止扩展，开始进行下一个字符串的扩展。扩展的起点是回文串的中心，中心有可能是s中的任意一处位置，所以需要对s从头至尾遍历作为中心。另外，这里的中心有可能是一个字符，也有可能是两个字符，所以在遍历时要分别将s[i]作为中心，和将s[i : i + 1]作为中心。

class Solution {
public:
    int extend(string& s, int left, int right) {
        int num = 0;
        while (left >= 0 && right < s.size() && s[left] == s[right]) {
            --left;
            ++right;
            ++num;
        }
        return num;
    }
    int countSubstrings(string s) {
        int ans = 0;
        for (int i = 0; i < s.size(); ++i) {
            ans += extend(s, i, i);
            ans += extend(s, i, i + 1);
        }
        return ans;
    }
};

        第2题（516. 最长回文子序列）相比上一题，将“连续的子串”改为了“非连续的子序列”，问题也从“回文子串的数量”变成了“最长回文子序列的长度”。有了上道题的经验，这道题也做出来了。因为问题的转变，所以定义方面，这道题的dp[i][j]（i ≥ j）变成了“s[i : j]的最长回文子串长度”。dp[i][j]同样分3种情况：

1. i与j相等，即s[i : j]就是一个字符。因为一个字符一定是回文串，所以dp[i][j]为1；
2. j等于(i + 1)，即s[i : j]是两个字符。那么dp[i][j]的取值就取决于s[i]与s[j]是否相等。相等就是2，否则是1；
3. 其他情况下，只有“s[i]与s[j]相等”时，s[i : j]才会相对于s[i + 1 : j - 1]多2个字符的回文子序列，dp[i : j]才会相对于dp[i + 1 : j - 1]增加2。否则，就相当于删去最左边字符或最右边字符，即从dp[i + 1][j]（注意这里不是dp[i - 1][j]）和dp[i][j - 1]中取较大值。

        这一题的dp依赖关系与上一题类似，情况3除了依赖其左下角的值外，还依赖于其左边和下边的值。所以综上，仍然需要初始化对角线（对应情况1），和对角线上每个位置右边的值（对应情况2）。实现中在循环遍历时初始化即可。遍历方向也与上一题一样，最后返回dp矩阵右下角的值作为结果。

class Solution {
public:
    int longestPalindromeSubseq(string s) {
        vectorint>> dp(s.size(), vector<int>(s.size()));
        for (int i = s.size() - 1; i >= 0; --i) {
            for (int j = i; j < s.size(); ++j) {
                if (j == i) {
                    dp[i][j] = 1;
                }
                else if (j == i + 1) {
                    if (s[j] == s[i]) {
                        dp[i][j] = 2;
                    }
                    else {
                        dp[i][j] = 1;
                    }
                }
                else 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][s.size() - 1];
    }
};