LeeCode 647. 回文子串

647. 回文子串 - 力扣（LeetCode）

动态规划法

动规五部曲：

1.确定dp数组及下标含义: 布尔类型的dp[i][j]：区间 [i,j] 的子串是否是回文子串；

2.确定递推公式：当s[i] = s[j]时，情况一：下标i 与 j相同，是回文子串；情况二：下标i 与 j相差为1，是回文子串；情况三：下标：i 与 j 相差大于1的时候，此时s[i]与s[j]已经相同了，区间是不是回文取决于dp[i + 1][j - 1]；

if (s[i] != s[j]) dp[i][j] = false;
if (s[i] == s[j]) {if (j - i <= 1) { // 情况一 和 情况二result++;dp[i][j] = true;} else if (dp[i + 1][j - 1]) { // 情况三result++;dp[i][j] = true;}
}

3.dp数组初始化：dp[i][j] = false;

4.确定遍历顺序：从左到右、从下到上遍历；

5.举例递推dp数组;

代码：

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 (s[i] == s[j]) {if (j - i <= 1) {result++;dp[i][j] = true;}else if (dp[i + 1][j - 1]) {result++;dp[i][j] = true;}}}}  return result;}
};

时间复杂度：O（n²）空间复杂度：O（n²）

双指针法

思路：

确定回文串即从中心向两边扩散看是否对称，中心点可由一个或两个元素组成。

代码：

class Solution {
public:int countSubstrings(string s) {int result = 0;for (int i = 0; i < s.size(); i++) {result += extend(s, i, i, s.size());result += extend(s, i, i + 1, s.size());}return result;}int extend(const string& s, int i, int j, int n) {int res = 0;while (i >= 0 && j < n && s[i] == s[j]) {i--; j++; res++;}return res;}
};

时间复杂度：O（n²）空间复杂度：O（1）

LeeCode 516.最长回文子序列

516. 最长回文子序列 - 力扣（LeetCode）

动规五部曲：

1.确定dp数组及下标含义: dp[i][j]：字符串s在[i, j]范围内最长的回文子序列的长度；

2.确定递推公式：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]);

3.dp数组初始化：if (i== j) dp[i][j] = 1; else dp[i][j] = 0;

4.确定遍历顺序：从左到右、从下到上遍历；

5.举例递推dp数组;

代码：

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

时间复杂度：O（n²）空间复杂度：O（n²）