代码随想录算法训练营第五十七天 | 647. 回文子串、516. 最长回文子序列

本文主要是介绍代码随想录算法训练营第五十七天 | 647. 回文子串、516. 最长回文子序列，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

647. 回文子串

题目链接：647. 回文子串

给你一个字符串 s ，请你统计并返回这个字符串中 回文子串 的数目。

回文字符串 是正着读和倒过来读一样的字符串。

子字符串 是字符串中的由连续字符组成的一个序列。

具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。

文章讲解/视频讲解：https://programmercarl.com/0647.%E5%9B%9E%E6%96%87%E5%AD%90%E4%B8%B2.html

思路与实现

设置一个二维bool类型的dp数组，dp[i][j]代表s的i到j范围的子串是否是回文子串。在dp数组递推时，有三种情况：

i == j，此时子串只有一个字符，dp[i][j] = true。
i + 1 == j，此时子串有两个字符，是否为回文子串取决于这两个字符是否相等，dp[i][j] = s[i] == s[j]。
i + 1 < j，此时子串大于两个字符，是否为回文子串不仅取决于s[i]与s[j]这两个字符是否相等，同时也取决于dp[i + 1][j - 1]。

由于dp[i][j]依赖于dp[i + 1][j - 1]，因此，遍历顺序应当是：i从大到小，j从小到大。

代码如下：

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

516. 最长回文子序列

题目链接：516. 最长回文子序列

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

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

文章讲解/视频讲解：https://programmercarl.com/0516.%E6%9C%80%E9%95%BF%E5%9B%9E%E6%96%87%E5%AD%90%E5%BA%8F%E5%88%97.html

思路与实现

设置一个二维dp数组，其中dp[i][j]代表i ~ j范围的s中，最长回文子序列长度。首先是初始化，当i == j时，只有一个字符，此时最长回文子序列长度为1，可以直接设置dp数组的所有位置为1。

接着讨论dp数组的递推：

当i + 1 == j时，此时有两个字符，如果这两个字符相等，则dp[i][j] = 2，如果不等，则dp[i][j] = 1。

当i + 1 < j时，此时大于两个字符，如果这两个字符相等，则dp[i][j] = dp[i + 1][j - 1] + 2，如果不等，可以选择丢弃左边的字符或者丢弃右边的字符，选择结果最大的值，即dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])。

由于dp[i][j]依赖于dp[i + 1][j - 1]，因此在遍历时，i从大到小遍历，j从小到大遍历。

代码如下：

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