当前位置:   article > 正文

代码随想录算法训练营第五十七天|647. 回文子串、516.最长回文子序列

代码随想录算法训练营第五十七天|647. 回文子串、516.最长回文子序列

LeetCode 647 回文子串

题目链接:https://leetcode.cn/problems/palindromic-substrings/

思路:

方法一:用二维整数数组记录回文子串个数

  • dp数组的含义
    d p [ i ] [ j ] dp[i][j] dp[i][j]代表是[i,j-1]中含有多少个回文子串

  • 递推公式
    本题有两种情况:
    s [ i , j − 1 ] s[i,j-1] s[i,j1]是回文子串
    显然此时递推公式为:
    d p [ i ] [ j ] = d p [ i ] [ j − 1 ] + 1 dp[i][j] = dp[i][j-1]+1 dp[i][j]=dp[i][j1]+1
    s [ i , j − 1 ] s[i,j-1] s[i,j1]不是回文子串
    此时递推公式为:
    d p [ i ] [ j ] = d p [ i ] [ j − 1 ] dp[i][j] = dp[i][j-1] dp[i][j]=dp[i][j1]

  • 初始化
    都初始化为0即可,因为在后面会被覆盖掉。

  • 遍历顺序
    显然遍历是从上到下,从左到右

代码:
class Solution {
public:
    int countSubstrings(string s) {
        vector<vector<int>>dp(s.size() + 1, vector<int>(s.size() + 1, 0));

        // for(int i = 1; i <= s.size(); i++)
        //     dp[i][i] = 1;
        
        for(int i = 0; i <= s.size(); i++)
        {
            for(int j = i + 1; j <= s.size(); j++)
            {
                if(isPalindromic(s, i, j - 1))
                    dp[i][j] = dp[i][j - 1] + 1;
                else
                    dp[i][j] = dp[i][j - 1];
            }
        }

        int result = 0;

        for(int i = 0; i <= s.size(); i++)
        {
            result += dp[i][s.size()];
            // cout << dp[i][s.size()];
        }
        return result;

    }

    bool isPalindromic(string s, int start, int end)
    {
        for(int i = start, j = end; i <= j; i++, j--)
        {
            if(s[i] != s[j])
                return false;
        }
        return true;
    }

};
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41

方法二:用二维布尔数组判断当前子串是否是回文子串

  • dp数组的含义
    d p [ i ] [ j ] dp[i][j] dp[i][j]代表[i,j]是否是回文子串

  • 递推公式
    本题有两种情况:
    s[i] == s[j]
    这个时候又有三种情况:
    1. i=j,例子:a;此时必然是回文子串
    2. j - i = 1,即:aa;此时同然是回文子串
    这两种情况递推公式都是
    d p [ i ] [ j ] = t r u e dp[i][j] =true dp[i][j]=true
    3. j- i > 1,即abcsda,这个时候就要判断[i+1,j-1]是否是回文子串了,如果是的话,那么[i,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;
    	}
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
  • 初始化
    因为如果不是回文子串的话,赋值为false即可,而且为了不被初始化影响,所以值都初始化为false

  • 遍历顺序
    由递推公式可知:

    如果这矩阵是从上到下,从左到右遍历,那么会用到没有计算过的 d p [ i + 1 ] [ j − 1 ] dp[i + 1][j - 1] dp[i+1][j1],也就是根据不确定是不是回文的区间[i+1,j-1],来判断了[i,j]是不是回文,那结果一定是不对的。

    所以一定要从下到上,从左到右遍历,这样保证 d p [ i + 1 ] [ j − 1 ] dp[i + 1][j - 1] dp[i+1][j1]都是经过计算的。

代码
class Solution {
public:
    int countSubstrings(string s) {
        int result = 0;
        vector<vector<bool>>dp(s.size(), vector<bool>(s.size(), false));

        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])
                        {
                            dp[i][j] = true;
                            result++;
                        }
                    }
                }
            }
        }

        return result;
    }
};
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32

总结

想到了第一种方法,但是时间和内存花费都比较大。


LeetCode 516 最长回文子序列

题目链接:https://leetcode.cn/problems/longest-palindromic-subsequence/

思路:

  • dp数组的含义
    dp[i][j]dp[i][j] 表示在[i,j]内最长的回文子序列长度

  • 递推公式
    本题要求的是子序列,和子串最大的不同就是,本题不需要连续
    本题主要还是看s[i]和s[j]是否相同
    s [ i ] = s [ j ] s[i]=s[j] s[i]=s[j]
    此时递推公式为:
    d p [ i ] [ j ] = d p [ i + 1 ] [ j − 1 ] + 2 dp[i][j]=dp[i+1][j-1]+2 dp[i][j]=dp[i+1][j1]+2
    (没想明白的话要看一看dp数组的含义)
    s [ i ] ! = s [ j ] s[i]!=s[j] s[i]!=s[j]
    此时要考虑,包含i,即[i,j-1]内最长的回文子序列长度和包含j,即[i+1,j]内最长的回文子序列长度中哪个更长
    所以递推公式为:
    d p [ i ] [ j ] = m a x ( d p [ i ] [ j − 1 ] , d p [ i + 1 ] [ j ] dp[i][j]=max(dp[i][j-1],dp[i+1][j] dp[i][j]=max(dp[i][j1],dp[i+1][j]

  • 初始化
    首先要考虑当i 和j 相同的情况,从递推公式: d p [ i ] [ j ] = d p [ i + 1 ] [ j − 1 ] + 2 dp[i][j] = dp[i + 1][j - 1] + 2 dp[i][j]=dp[i+1][j1]+2; 可以看出 递推公式是计算不到 i 和j相同时候的情况。
    所以需要手动初始化一下,当i与j相同,那么 d p [ i ] [ j ] dp[i][j] dp[i][j]一定是等于1的,即:一个字符的回文子序列长度就是1。
    其他情况dp[i][j]初始为0就行,这样递推公式: d p [ i ] [ j ] = m a x ( d p [ i + 1 ] [ j ] , d p [ i ] [ j − 1 ] ) dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]) dp[i][j]=max(dp[i+1][j],dp[i][j1]) d p [ i ] [ j ] dp[i][j] dp[i][j]才不会被初始值覆盖。

  • 遍历顺序

    由图片可知, d p [ i ] [ j ] dp[i][j] dp[i][j]依赖于 d p [ i + 1 ] [ j − 1 ] dp[i + 1][j - 1] dp[i+1][j1], d p [ i + 1 ] [ j ] dp[i + 1][j] dp[i+1][j] d p [ i ] [ j − 1 ] dp[i][j - 1] dp[i][j1],所以要从下往上,再从左到右。

代码:

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];
    }
};
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22

总结

子序列和子串的最大不同就在于子序列可以不连续


今日总结:

动态规划结束了!

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/我家小花儿/article/detail/498833
推荐阅读
相关标签
  

闽ICP备14008679号