笔记:代码随想录算法训练营day46:LeetCode647. 回文子串\516.最长回文子序列

学习资料:代码随想录

647. 回文子串

力扣题目链接

其实个人感觉这里的动规也是一个双指针的方法

// 定义：dp[i][j]表示区间范围为[i,j]左闭右闭的子串是否为回文子串，布尔类型
// 递推公式：如过s[i]==s[j],那么i,j包括两个数或1个数的情况是回文子串，如果包含超过两个数，那么dp[i+1][j-1]是true的话，也返回true，当然不相等就直接false了
// 初始化：可以先都初始化为false
// 遍历顺序：看递推公式
// 打印

// 定义：dp[i][j]表示区间范围为[i,j]左闭右闭的子串是否为回文子串，布尔类型
// 递推公式：如过s[i]==s[j],那么i,j包括两个数或1个数的情况是回文子串，如果包含超过两个数，那么dp[i+1][j-1]是true的话，也返回true，当然不相等就直接false了
// 初始化：可以先都初始化为false
// 遍历顺序：看递推公式
// 打印
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();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]){
                        dp[i][j]=true;
                        result++;
                    }
                }
            }
        }
        return result;
    }
};

双指针:从中心往两边扩散,以一个数为中心时处理的是奇数的回文子串,以两个数为中心时处理的是偶数的回文子串

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());     //处理奇数回文子串，如aba
            result+=extend(s,i,i+1,s.size());   //处理偶数回文子串，如abba
        }
        return result;
    }
    int extend(const string& s,int i,int j,int n){
        int res;
        while(i>=0&&j<n&&s[i]==s[j]){
            i--;
            j++;
            res++;
        }
        return res;
    }
};

516.最长回文子序列

力扣题目链接

思路:

// 定义：dp[i][j]表示区间[i][j]左闭右闭内的最长回文子序列

// 递推公式：如果s[i]==s[j],那么当前的长度是上一状态dp[i+1][j-1]再加上两个长度，有一种向两侧扩散比较的感觉，否则，就比较去掉s[i]或s[j]的状态，继承dp[i+1][j]或dp[i][j-1].

// 初始化：dp[i][j]在i=j的时候都得是1，首先看递推公式，i=0的话访问j如果从0开始遍历，那访问-1肯定是访问不到，j从j+1开始遍历，这样的话，dp[i][i] 的情况是遍历不到的.或者就单看dp[i][j] = dp[i + 1][j - 1] + 2，也没有遍历dp[i][i]的准备

// 遍历顺序,j要从i+1开始遍历了

// 打印

// 定义：dp[i][j]表示区间[i][j]左闭右闭内的最长回文子序列
// 递推公式：如果s[i]==s[j],那么当前的长度是上一状态dp[i+1][j-1]再加上两个长度，有一种向两侧扩散比较的感觉，否则，就比较去掉s[i]或s[j]的状态，继承dp[i+1][j]或dp[i][j-1].
// 初始化：dp[i][j]在i=j的时候都得是1，首先看递推公式，i=0的话访问j如果从0开始遍历，那访问-1肯定是访问不到，j要从j+1开始遍历，这样的话，dp[i][i] 的情况是遍历不到的.或者就单看dp[i][j] = dp[i + 1][j - 1] + 2，也没有遍历dp[i][i]的准备
// 遍历顺序,j要从i+1开始遍历了
// 打印
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][j-1],dp[i+1][j]);
                }
            }
        }
        return dp[0][s.size()-1];
    }
};

其实也可以用上一题的方法来初始化,也AC了

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;j<s.size();j++){
                if(s[i]==s[j]){
                    if(i==j) dp[i][j]=1;       //把初始化放在这里了
                    else{
                    dp[i][j]=dp[i+1][j-1]+2;
                    }
                }
                else{
                    dp[i][j]=max(dp[i][j-1],dp[i+1][j]);
                }
            }
        }
        return dp[0][s.size()-1];
    }