JLUVicent

647回文子串&516最长回文子序列

 
  • 2023年 04月12日
  • 0 阅读

day57

647.回文子串

题目链接：647. 回文子串

解题思路：参考 视频

1.确定dp数组及下标含义

定义二维dp数组dp[i][j]表示以[i,j]为区间的子串是否为回文串，是返回true，否则为false

2.递推公式

只有当s[i] == s[j]才能判断是否为回文串

  • i == j 时候：dp[i][j] = true;
  • j - i = 1：dp[i][j] = true;
  • 其他情况：dp[i][j] = true 前提是保证dp[i+1][j-1] = true;

image-20230412085342796

3.初始化

dp[i][j] = false;全部初始化为false；

4.确定遍历顺序

647.回文子串

如上图所示，根据推导过程，遍历顺序为从下到上，从左到右

5.打印dp数组

647.回文子串1

class Solution {
public:
    int countSubstrings(string s) {
        vector<vector<bool>> dp(s.size(),vector(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){
                        dp[i][j] = true;
                        result++;
                    }else if( dp[i+1][j-1] == true){
                        dp[i][j] = true;
                        result++;
                    }
                }
            }
        }
        return result;
    }
};

516.最长回文子序列

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

解题思路：参考 视频

1.dp数组及下标的含义

dp[i][j]： [i,j]为区间的字符串中最长的回文子序列数

2.递推公式

s[i] == s[j] ： dp[i][j] = dp[i+1][j-1] + 2

s[i] != s[j] ： max( dp[i+1][j],dp[i][j-1])，分别取s[i],s[j]两个取最大值

3.初始化

初始化i == j 时候的情况 dp[i][i] = 1;

4.遍历顺序

从下到上，从左到右，根据递推公式得到

5.打印dp数组

516.最长回文子序列3

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];
    }
};
搜索