*算法训练（leetcode）第四十天 | 647. 回文子串、516. 最长回文子序列
刷题记录
- *647. 回文子串
- *516. 最长回文子序列
*647. 回文子串
leetcode题目地址
dp[i][j]存储 i-j 的子串是否是回文串。使用额外的计数器对回文串个数进行记录。
单个字符本身就是回文子串。当子串长度大于1时，两侧的字符相同，则需要判断中间的子串是否是回文串。
时间复杂度： O ( n ) O(n) O(n)
空间复杂度： O ( n ) O(n) O(n)
// c++
class Solution {
public:int countSubstrings(string s) {vector<vector<bool>> dp(s.size()+1, vector<bool>(s.size()+1, 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){dp[i][j] = true;result++;}else if(dp[i+1][j-1]) {result++;dp[i][j] = true;}}}}return result;}
};
*516. 最长回文子序列
leetcode题目地址
求的是最长回文子序列而不是子串，因此不需要连续。
dp[i][j]存储的是字符串 s 中 i-j 之间的最长回文子序列长度。
- 当s[i] != s[j]时，dp[i][j] = max(dp[i][j-1], dp[i+1][j]);
- 当s[i] == s[j]时，有两种情况：
- j-i <= 1，即j和i指向同一个字符或相邻的两个字符，则最长子序列长度为1（同一字符）或2（相邻两个字符）：
- dp[i][j] = j - i + 1;
- j-i > 1，则需要查看中间子串的最长回文子序列的长度，用中间串的最长回文子序列的长度加上当前两个字符（i和j指向的字符）
- dp[i][j] = dp[i+1][j-i] + 2;
- j-i <= 1，即j和i指向同一个字符或相邻的两个字符，则最长子序列长度为1（同一字符）或2（相邻两个字符）：
时间复杂度： O ( n 2 ) O(n^2) O(n2)
空间复杂度： O ( n 2 ) O(n^2) O(n2)
// c++
class Solution {
public:int longestPalindromeSubseq(string s) {vector<vector<int>> dp(s.size()+1, vector<int>(s.size()+1, 0));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]) dp[i][j] = max(dp[i][j-1], dp[i+1][j]);else{if(j-i<=1) dp[i][j] = j-i+1;else dp[i][j] = dp[i+1][j-1]+2;}if(dp[i][j]>result) result = dp[i][j];}/*// 输出dpfor(int j=0; j<s.size(); j++) cout<<dp[i][j]<<" ";cout<<endl;*/}return result;}
};
动态规划系列完结