当前位置:   article > 正文

算法沉淀——动态规划之回文串问题(上)(leetcode真题剖析)

算法沉淀——动态规划之回文串问题(上)(leetcode真题剖析)

在这里插入图片描述

01.回文子串

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

给你一个字符串 s ,请你统计并返回这个字符串中 回文子串 的数目。

回文字符串 是正着读和倒过来读一样的字符串。

子字符串 是字符串中的由连续字符组成的一个序列。

具有不同开始位置或结束位置的子串,即使是由相同的字符组成,也会被视作不同的子串。

示例 1:

输入:s = "abc"
输出:3
解释:三个回文子串: "a", "b", "c"
  • 1
  • 2
  • 3

示例 2:

输入:s = "aaa"
输出:6
解释:6个回文子串: "a", "a", "a", "aa", "aa", "aaa"
  • 1
  • 2
  • 3

提示:

  • 1 <= s.length <= 1000
  • s 由小写英文字母组成

思路

  1. 预处理回文信息: 创建一个 dp 表,其中 dp[i][j] 表示字符串 s 中子串 s[i:j+1] 是否是回文串。

  2. 状态转移方程: 对于回文串,分析两头的元素:

    • 如果 s[i] != s[j],则不可能是回文串,dp[i][j] = 0

    • 如果

      s[i] == s[j]
      
      • 1

      ,则根据长度分三种情况讨论:

      • 如果长度为 1,即 i == j,则一定是回文串,dp[i][j] = true
      • 如果长度为 2,即 i + 1 == j,则也一定是回文串,dp[i][j] = true
      • 如果长度大于 2,则需要看 [i + 1, j - 1] 区间的子串是否回文,dp[i][j] = dp[i + 1][j - 1]
  3. 初始化: 由于状态转移方程已经考虑了各种情况,无需额外初始化。

  4. 填表顺序: 根据状态转移方程,从下往上填写每一行。

  5. 返回值: 根据状态表达和题目要求,返回 dp 表中 true 的个数。

代码

class Solution {
public:
    int countSubstrings(string s) {
        int n=s.size();
        vector<vector<bool>> dp(n,vector<bool>(n));

        int sum=0;
        for(int i=n-1;i>=0;i--){
            for(int j=i;j<n;j++){
                if(s[i]==s[j]) dp[i][j]=i+1<j?dp[i+1][j-1]:true;
                if(dp[i][j]) sum++;
            }
        }
        return sum;
    }
};
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16

02.最长回文子串

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

给你一个字符串 s,找到 s 中最长的回文子串。

如果字符串的反序与原始字符串相同,则该字符串称为回文字符串

示例 1:

输入:s = "babad"
输出:"bab"
解释:"aba" 同样是符合题意的答案。
  • 1
  • 2
  • 3

示例 2:

输入:s = "cbbd"
输出:"bb"
  • 1
  • 2

提示:

  • 1 <= s.length <= 1000
  • s 仅由数字和英文字母组成

思路

和上一题思路基本一致,但这里我们要返回字串,所以我们需要在原有算法上标记字串的开始位置和子串的长度。

代码

class Solution {
public:
    string longestPalindrome(string s) {
        int n=s.size();
        vector<vector<bool>> dp(n,vector<bool>(n));

        int len=1,begin=0;
        for(int i=n-1;i>=0;--i){
            for(int j=i;j<n;++j){
                if(s[i]==s[j]) dp[i][j]=i+1<j?dp[i+1][j-1]:true;
                if(dp[i][j]&&j-i+1>len) len=j-i+1,begin=i;
            }
        }
        return s.substr(begin,len);
    }
};
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16

03.分割回文串 IV

题目链接:https://leetcode.cn/problems/palindrome-partitioning-iv/

给你一个字符串 s ,如果可以将它分割成三个 非空 回文子字符串,那么返回 true ,否则返回 false

当一个字符串正着读和反着读是一模一样的,就称其为 回文字符串

示例 1:

输入:s = "abcbdd"
输出:true
解释:"abcbdd" = "a" + "bcb" + "dd",三个子字符串都是回文的。
  • 1
  • 2
  • 3

示例 2:

输入:s = "bcbddxy"
输出:false
解释:s 没办法被分割成 3 个回文子字符串。
  • 1
  • 2
  • 3

提示:

  • 3 <= s.length <= 2000
  • s 只包含小写英文字母。

思路

其实这里我们可以依照第一题的解法将所有的子串都进行统计,再遍历计算每个分割位置组成的3个子串是否都符合回文子串即可。

代码

class Solution {
public:
    bool checkPartitioning(string s) {
        int n=s.size();
        vector<vector<bool>> dp(n,vector<bool>(n));
        for(int i=n-1;i>=0;--i)
            for(int j=i;j<n;j++)
                if(s[i]==s[j]) dp[i][j]=i+1<j?dp[i+1][j-1]:true;
        
        for(int i=1;i<n-1;i++)
            for(int j=i;j<n-1;++j)
                if(dp[0][i-1]&&dp[i][j]&&dp[j+1][n-1]) return true;
        return false;
    }
};
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15

04.分割回文串 II

题目链接:https://leetcode.cn/problems/palindrome-partitioning-ii/

给你一个字符串 s,请你将 s 分割成一些子串,使每个子串都是回文。

返回符合要求的 最少分割次数

示例 1:

输入:s = "aab"
输出:1
解释:只需一次分割就可将 s 分割成 ["aa","b"] 这样两个回文子串。
  • 1
  • 2
  • 3

示例 2:

输入:s = "a"
输出:0
  • 1
  • 2

示例 3:

输入:s = "ab"
输出:1
  • 1
  • 2

提示:

  • 1 <= s.length <= 2000
  • s 仅由小写英文字母组成

思路

  1. 状态表达:i 位置为结尾,定义状态表达 dp[i] 表示字符串 s[0, i] 区间上的字符串,最少分割的次数。

  2. 状态转移方程: 通常考虑最后一个位置的信息。设 0 <= j <= i,那么可以根据 [j, i] 位置上的子串是否是回文串分成以下两类:

    • 如果 [j, i] 位置上的子串能够构成一个回文串,那么 dp[i] 就等于 [0, j - 1] 区间上最少回文串的个数 + 1,即 dp[i] = dp[j - 1] + 1
    • 如果 [j, i] 位置上的子串不能构成一个回文串,此时 j 位置就不用考虑。

    由于求的是最小值,因此需要循环遍历 j 的取值,取最小值。

  3. 优化: 在状态转移方程中,需要快速判断字符串中的子串是否回文。因此,可以先处理一个 dp 表,其中保存所有子串是否回文的信息。

  4. 初始化: 在循环遍历 j 之前,处理 j == 0 的情况。此时,表示的区间是 [0, i]。如果 [0, i] 区间上的字符串已经是回文串了,最小的回文串就是 1j 往后的值就不用遍历了。为防止在求 min 操作时,0 干扰结果,将表中的值初始化为「无穷大」。

  5. 填表顺序: 从左往右填写。

  6. 返回值: 根据状态表达,返回 dp[n - 1]

代码

class Solution {
public:
    int minCut(string s) {
        int n=s.size();
        vector<vector<bool>> isp(n,vector<bool>(n));
        for(int i=n-1;i>=0;--i)
            for(int j=i;j<n;j++)
                if(s[i]==s[j]) isp[i][j]=i+1<j?isp[i+1][j-1]:true;

        vector<int> dp(n,INT_MAX);
        for(int i=0;i<n;++i){
            if(isp[0][i]) dp[i]=0;
            else{
                for(int j=1;j<=i;j++)
                    if(isp[j][i]) dp[i]=min(dp[i],dp[j-1]+1);
            }
        }
        return dp[n-1];
    }
};
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20

05.最长回文子序列

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

给你一个字符串 s ,找出其中最长的回文子序列,并返回该序列的长度。

子序列定义为:不改变剩余字符顺序的情况下,删除某些字符或者不删除任何字符形成的一个序列。

示例 1:

输入:s = "bbbab"
输出:4
解释:一个可能的最长回文子序列为 "bbbb" 。
  • 1
  • 2
  • 3

示例 2:

输入:s = "cbbd"
输出:2
解释:一个可能的最长回文子序列为 "bb" 。 
  • 1
  • 2
  • 3

提示:

  • 1 <= s.length <= 1000
  • s 仅由小写英文字母组成

思路

  1. 状态表达:i 位置为结尾,定义状态表达 dp[i][j] 表示字符串 s[i, j] 区间内的所有子序列中,最长的回文子序列的长度。

  2. 状态转移方程: 回文子序列和回文子串的分析方式一般都是选择这段区域的「左右端点」的字符情况来分析。因为如果一个序列是回文串的话,「去掉首尾两个元素之后依旧是回文串」,「首尾加上两个相同的元素之后也依旧是回文串」。根据首尾元素的不同,分为以下两种情况:

    • s[i] == s[j] 时,[i, j] 区间上的最长回文子序列,应该是 [i + 1, j - 1] 区间内的那个最长回文子序列首尾填上 s[i]s[j],此时 dp[i][j] = dp[i + 1][j - 1] + 2
    • s[i] != s[j] 时,这两个元素就不能同时添加在一个回文串的左右,那么就应该让 s[i] 单独加在一个序列的左边,或者让 s[j] 单独放在一个序列的右边,看看这两种情况下的最大值:
      • 单独加入 s[i] 后的区间在 [i, j - 1],此时最长的回文序列的长度就是 dp[i][j - 1]
      • 单独加入 s[j] 后的区间在 [i + 1, j],此时最长的回文序列的长度就是 dp[i + 1][j]

    取两者的最大值,于是 dp[i][j] = max(dp[i][j - 1], dp[i + 1][j])

  3. 初始化: 需要处理两种边界情况:

    • i == j 时,区间内只有一个字符,此时 dp[i][j] = 1
    • i + 1 == j 时,区间内有两个字符,如果这两个字符相同,dp[i][j] = 2,否则 dp[i][j] = 0

    在填表的时候,可以同步处理第一种边界情况,对于第二种边界情况,dp[i + 1][j - 1] 的值为 0,不会影响最终的结果,因此可以不用考虑。

  4. 填表顺序: 根据「状态转移」,dp[i + 1] 表示下一行的位置,dp[j - 1] 表示前一列的位置。因此填表顺序应该是「从下往上填写每一行」,「每一行从左往右」。

  5. 返回值: 根据「状态表达」,返回 [0, n -1] 区域上的最长回文序列的长度,因此需要返回 dp[0][n - 1]

代码

class Solution {
public:
    int longestPalindromeSubseq(string s) {
        int n=s.size();
        vector<vector<int>> dp(n,vector<int>(n));

        for(int i=n-1;i>=0;i--){
            dp[i][i]=1;
            for(int j=i+1;j<n;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][n-1];
    }
};
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16

06.让字符串成为回文串的最少插入次数

题目链接:https://leetcode.cn/problems/minimum-insertion-steps-to-make-a-string-palindrome/

给你一个字符串 s ,每一次操作你都可以在字符串的任意位置插入任意字符。

请你返回让 s 成为回文串的 最少操作次数

「回文串」是正读和反读都相同的字符串。

示例 1:

输入:s = "zzazz"
输出:0
解释:字符串 "zzazz" 已经是回文串了,所以不需要做任何插入操作。
  • 1
  • 2
  • 3

示例 2:

输入:s = "mbadm"
输出:2
解释:字符串可变为 "mbdadbm" 或者 "mdbabdm" 。
  • 1
  • 2
  • 3

示例 3:

输入:s = "leetcode"
输出:5
解释:插入 5 个字符后字符串变为 "leetcodocteel" 。
  • 1
  • 2
  • 3

提示:

  • 1 <= s.length <= 500
  • s 中所有字符都是小写字母。

思路

  1. 状态表达:i 位置为结尾,定义状态表达 dp[i][j] 表示字符串 s[i, j] 区域成为回文子串的最少插入次数。
  2. 状态转移方程: 回文子序列和回文子串的分析方式一般都是选择这段区域的「左右端点」的字符情况来分析。因为如果一个序列是回文串的话,「去掉首尾两个元素之后依旧是回文串」,「首尾加上两个相同的元素之后也依旧是回文串」。根据首尾元素的不同,可以分为以下两种情况:
    • s[i] == s[j] 时,[i, j] 区间内成为回文子串的最少插入次数,取决于 [i + 1, j - 1] 区间内成为回文子串的最少插入次数。若 i >= j - 1i == j - 1[i + 1, j - 1] 不构成合法区间),此时只有 1 ~ 2 个相同的字符, [i, j] 区间一定是回文子串,成为回文子串的最少插入次数是 0。此时 dp[i][j] = i >= j - 1 ? 0 : dp[i + 1][j - 1]
    • s[i] != s[j] 时,需要在区间的最右边或最左边插入一个字符,取决于 [i + 1, j][i, j + 1] 区间内成为回文子串的最少插入次数。此时 dp[i][j] = min(dp[i + 1][j], dp[i][j - 1]) + 1
  3. 初始化: 根据「状态转移方程」,没有不能递推表达的值,无需初始化。
  4. 填表顺序: 根据「状态转移」,dp[i + 1] 表示下一行的位置,dp[j - 1] 表示前一列的位置。因此填表顺序应该是「从下往上填写每一行」,「每一行从左往右」。
  5. 返回值: 根据「状态表达」,返回 [0, n - 1] 区域上成为回文子串的最少插入次数,因此需要返回 dp[0][n - 1]

代码

class Solution {
public:
    int minInsertions(string s) {
        int n=s.size();
        vector<vector<int>> dp(n,vector<int>(n));

        for(int i=n-1;i>=0;i--){
            for(int j=i+1;j<n;j++){
                if(s[i]==s[j]) dp[i][j]=dp[i+1][j-1];
                else dp[i][j]=min(dp[i+1][j],dp[i][j-1])+1;
            }
        }
        return dp[0][n-1];
    }
};
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/Gausst松鼠会/article/detail/198598
推荐阅读
相关标签
  

闽ICP备14008679号