647. 回文子串
思路:
dp[i][j]
表示s[i~j]
的字符串是否是回文串- 递推公式:如果
s[i] == s[j]
,判断开区间(i, j)
是不是回文串
i == j
单个的字符都是回文串j - i == 1
以两个相同字符为中心的回文串dp[i+1][j-1]
长度超过3个回文串去掉首尾其内部也是回文串
- 初始化,一开始初始化为每个字符串都不是回文串,然后开始遍历更新结果
- 递推顺序:要用到下一行
i+1
的数据,所以递推在二维数组中从下往上,从左往右
class Solution {
public:
int countSubstrings(string s) {
int s_len = s.length();
int ans = 0;
vector<vector<bool>> dp(s_len, vector<bool>(s_len, false));
for (int i = s_len - 1; i >= 0; i--) {
for (int j = i; j < s_len; j++) {
if (s[i] == s[j]) {
if (j - i <= 1) {
ans++;
dp[i][j] = true;
} else if (dp[i + 1][j - 1]) {
dp[i][j] = true;
ans++;
}
}
}
}
return ans;
}
};
516. 最长回文子序列
思路:
子串必须是连续的,而这里的子序列可以不连续
dp[i][j]
表示s[i~j]
中的最长回文子序列的长度- 递推公式
s[i] == s[j]
全部加入回文串,使回文串长度加2,dp[i][j] = dp[i+1][j-1]+2
s[i] != s[j]
选择一个让最大回文串更长的字符加入,dp[i][j] = max(dp[i+1][j], dp[i][j-1])
- 初始化每个单个字符的为回文串,
dp[i][j] = 1
- 递推顺序从左下到右上
class Solution {
public:
int longestPalindromeSubseq(string s) {
int s_len = s.length();
vector<vector<int>> dp(s_len, vector<int>(s_len, 0));
for (int i = 0; i < s_len; i++) dp[i][i] = 1;
for (int i = s_len - 1; i >= 0; i--) {
for (int j = i + 1; j < s_len; 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]);
}
}
return dp[0][s_len - 1];
}
};