Monodyee

这个屌丝很懒，什么也没留下！

热门标签

【算法专题】动态规划之回文子串问题_回文子串个数动态规划

作者：Monodyee | 2024-04-28 13:33:58

踩

回文子串个数动态规划

动态规划6.0

动态规划 - - - 回文子串问题

动态规划 - - - 回文子串问题

1. 回文子串

题目链接 -> Leetcode -647.回文子串

Leetcode -647.回文子串

题目：给你一个字符串 s ，请你统计并返回这个字符串中回文子串的数目。
回文字符串是正着读和倒过来读一样的字符串。
子字符串是字符串中的由连续字符组成的一个序列。
具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。

示例 1：
输入：s = “abc”
输出：3
解释：三个回文子串 : “a”, “b”, “c”

示例 2：
输入：s = “aaa”
输出：6
解释：6个回文子串 : “a”, “a”, “a”, “aa”, “aa”, “aaa”

提示：

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

思路：我们可以先预处理一下，将所有子串「是否回文」的信息统计在 dp 表里面，然后直接在表里面统计 true 的个数即可；

状态表示：为了能表示出来所有的子串，我们可以创建⼀个 n * n 的二维 dp 表，只用到「上三角部分」即可。所以状态表示：

dp[i][j] 表示： s 字符串 [i, j] 的子串，是否是回文串.

状态转移方程：对于回文串，我们一般分析一个「区间两头」的元素：

当 s[i] != s[j] 的时候：不可能是回文串， dp[i][j] = false；
当 s[i] == s[j] 的时候：根据长度分三种情况讨论：
• 长度为 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] 。

综上，状态转移方程分情况谈论即可；

返回值：根据「状态表示和题目要求」，我们需要返回 dp 表中 true 的个数。

代码如下：

		class Solution {
		public:
		    int countSubstrings(string s) 
		    {
		        int n = s.size();
		        vector<vector<bool>> dp(n, vector<bool>(n));
		        
		        //  dp[i][j] 表示： s 字符串 [i, j] 的子串，是否是回文串
		        int ans = 0;
		        for(int i = n - 1; i >= 0; i--)
		        {
		            for(int j = i; j < n; j++)
		            {
		                if(s[i] == s[j])
		                {
		                    if(i == j) dp[i][j] = true; // 一个字符也是回文串
		                    else if(i + 1 == j) dp[i][j] = true; // 两个字符
		                    else dp[i][j] = dp[i + 1][j - 1]; // 大于两个字符就判断减去这两个字符之后是否还是回文串
		                }
		                
		                if(dp[i][j]) ans++;
		            }
		        }
		        return ans;
		    }
		};
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

2. 最长回文子串

题目链接 -> Leetcode -5.最长回文子串

Leetcode -5.最长回文子串

题目：给你一个字符串 s，找到 s 中最长的回文子串。

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

示例 1：
输入：s = “babad”
输出：“bab”
解释：“aba” 同样是符合题意的答案。

示例 2：
输入：s = “cbbd”
输出：“bb”

提示：

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

思路：思路与上题思路类似，我们可以先用 dp 表统计出「所有子串是否回文」的信息；然后根据 dp 表示 true 的位置，得到回文串的「起始位置」和「长度」。那么我们就可以在表中找出最长回文串。

代码如下：

		class Solution {
		public:
		    string longestPalindrome(string s) 
		    {
		        int n = s.size();
		        vector<vector<bool>> dp(n, vector<bool>(n));
		
		        int retlen = INT_MIN, begin = 0;
		
		        for(int i = n - 1; i >= 0; i--)
		        {
		            for(int j = i; j < n; j++)
		            {
		                // 标记回文串的位置
		                if(s[i] == s[j])
		                {
		                    if(i == j) dp[i][j] = true;
		                    else if(i + 1 == j) dp[i][j] = true;
		                    else dp[i][j] = dp[i + 1][j - 1];
		                }
		
		                // 如果以 i、j 位置为头和尾组成回文串，那么判断当前回文串的长度和 retlen 的长度，取其中的较大值，并记录长度和头的位置
		                if(dp[i][j] && j - i + 1 > retlen)
		                {
		                    retlen = j - i + 1;
		                    begin = i;
		                }
		            }
		        }
		        return s.substr(begin, retlen);
		    }
		};
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

3. 分割回文串Ⅳ

题目链接 -> Leetcode -1745.分割回文串Ⅳ

Leetcode -1745.分割回文串Ⅳ

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

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

示例 1：
输入：s = “abcbdd”
输出：true
解释：“abcbdd” = “a” + “bcb” + “dd”，三个子字符串都是回文的。

示例 2：
输入：s = “bcbddxy”
输出：false
解释：s 没办法被分割成 3 个回文子字符串。

提示：

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

思路：本题思路其实我们可以把它拆成「两个小问题」：

动态规划求解字符串中的一段非空子串是否是回文串；
枚举三个子串除字符串端点外的起止点，查询这三段非空子串是否是回文串；

代码如下：

		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])
		                {
		                    if(i == j || i + 1 == j) dp[i][j] = true;
		                    else dp[i][j] = dp[i + 1][j - 1];
		                }
		            }
		        }
		
		        // 将dp数组分为三段，枚举三个⼦串除字符串端点外的起⽌点，查询这三段⾮空⼦串是否是回⽂串
		        for(int i = 1; i < n - 1; i++)
		        {
		            for(int j = i; j < n - 1; j++)
		            {
		                if(dp[i][j] && dp[0][i - 1] && dp[j + 1][n - 1]) return true;
		            }
		        }
		
		        return false;
		    }
		};
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

4. 分割回文串Ⅱ

题目链接 -> Leetcode -132.分割回文串Ⅱ

Leetcode -132.分割回文串Ⅱ

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

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

示例 1：
输入：s = “aab”
输出：1
解释：只需一次分割就可将 s 分割成[“aa”, “b”] 这样两个回文子串。

示例 2：
输入：s = “a”
输出：0

示例 3：
输入：s = “ab”
输出：1

提示：

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

思路：

状态表示：根据经验，继续尝试用 i 位置为结尾，定义状态表示：

dp[i] 表示： s 中 [0, i] 区间上的字符串，最少分割的次数；

状态转移方程：状态转移方程一般都是根据「最后一个位置」的信息来分析：设 0 <= j <= i ，那么我们可以根据 j ~ i 位置上的子串是否是回文串分成下面两类：

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

由于我们要的是最小值，因此应该循环遍历一遍 j 的取值，拿到里面的最小值即可；

返回值：根据「状态表示」，应该返回 dp[n - 1]；

代码如下：

		class Solution {
		public:
		    int minCut(string s) 
		    {
		        int n = s.size();
		        vector<vector<bool>> isPal(n, vector<bool>(n));
		
		        // 1.是否是回文串
		        for(int i = n - 1; i >= 0; i--)
		        {
		            for(int j = i; j < n; j++)
		            {
		                if(s[i] == s[j])
		                    if(i == j || i + 1 == j) isPal[i][j] = true;
		                    else isPal[i][j] = isPal[i + 1][j - 1];
		            }
		        }
		
		        // dp[i] 表⽰： s 中 [0, i] 区间上的字符串，最少分割的次数
		        vector<int> dp(n, INT_MAX);// 最少分割次数
		        // 2.处理最少分割次数
		        for(int i = 0; i < n; i++)
		        {
		            // 0-i 位置是回文串
		            if(isPal[0][i]) 
		            {
		                dp[i] = 0;
		            }
		
		            // 0-i 位置不是回文串，分割
		            else
		            {
		                for(int j = i; j > 0; j--)
		                    // j - i 位置是回文串
		                    if(isPal[j][i]) 
		                        dp[i] = min(dp[j-1] + 1, dp[i]); // dp[j-1] + 1 就是 [0, j - 1] 区间上最少回⽂串的个数 + 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
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

5. 最长回文子序列

题目链接 -> Leetcode -516.最长回文子序列

Leetcode -516.最长回文子序列

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

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

示例 1：
输入：s = “bbbab”
输出：4
解释：一个可能的最长回文子序列为 “bbbb” 。

示例 2：
输入：s = “cbbd”
输出：2
解释：一个可能的最长回文子序列为 “bb” 。

提示：

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

思路：

状态表示：关于「单个字符串」问题中的「回文子序列」，或者「回文子串」，我们的状态表示研究的对象一般都是选取原字符串中的一段区域 [i, j] 内部的情况。这里我们继续选取字符串中的一段区域来研究：

dp[i][j] 表示：s 字符串 [i, j] 区间内的所有的子序列中，最长的回文子序列的长度；

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

当首尾两个元素「相同」的时候，也就是 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] 单独放在一个序列的右边，看看这两种情况下的最大值：
a. 单独加入 s[i] 后的区间在 [i, j - 1] ，此时最长的回文序列的长度就是 dp[i][j - 1] ；
b. 单独加入 s[j] 后的区间在 [i + 1, j] ，此时最长的回文序列的长度就是 dp[i + 1][j] ；

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

综上所述，状态转移方程为：

当 s[i] == s[j] 时： dp[i][j] = dp[i + 1][j - 1] + 2
当 s[i] != s[j] 时： dp[i][j] = max(dp[i][j - 1], dp[i + 1][j])

返回值：根据「状态表示」，我们需要返回 [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));
		
		        // dp[i][j] 表示s字符串[i，j]区间内所有子序列中最长回文子序列的长度
		        for(int i = n - 1; i >= 0; i--)
		        {
		            for(int j = i; j < n; j++)
		            {
		                if(s[i] == s[j])
		                {
		                    if(i == j) dp[i][j] = 1;
		                    else if(i + 1 == j) dp[i][j] = 2;
		                    else dp[i][j] = dp[i + 1][j - 1] + 2;
		                }
		                
		                // 如果s[i] != s[j]，说明回文子序列一定不能同时以 i 和 j 为结尾
		                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
17
18
19
20
21
22
23
24
25
26
27
28
29

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

题目链接 -> Leetcode -1312.让字符串成为回文串的最少插入次数

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

题目：给你一个字符串 s ，每一次操作你都可以在字符串的任意位置插入任意字符。
请你返回让 s 成为回文串的最少操作次数。
「回文串」是正读和反读都相同的字符串。

示例 1：
输入：s = “zzazz”
输出：0
解释：字符串 “zzazz” 已经是回文串了，所以不需要做任何插入操作。

示例 2：
输入：s = “mbadm”
输出：2
解释：字符串可变为 “mbdadbm” 或者 “mdbabdm” 。

示例 3：
输入：s = “leetcode”
输出：5
解释：插入 5 个字符后字符串变为 “leetcodocteel” 。

提示：

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

思路：

状态表示：dp[i][j] 表示字符串 [i, j] 区域成为回文子串的最少插入次数；
状态转移方程：关于「回文子序列」和「回文子串」的分析方式，一般都是比较固定的，都是选择这段区域的「左右端点」的字符情况来分析。因为如果一个序列是回文串的话，「去掉首尾两个元素之后依旧是回文串」，「首尾加上两个相同的元素之后也依旧是回文串」。因为，根据「首尾元素」的不同，可以分为下面两种情况：

当首尾两个元素「相同」的时候，也就是 s[i] == s[j] ：
a. 那么 [i, j] 区间内成为回文子串的最少插入次数，取决于 [i + 1, j - 1] 区间内成为回文子串的最少插入次数；
b. 若 i == j 或 i == 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] ：
a. 此时可以在区间最右边补上一个 s[i] ，需要的最少插入次数是 [i + 1, j] 成为回文子串的最少插入次数 + 本次插入，即 dp[i][j] = dp[i + 1][j] + 1 ；
b. 此时可以在区间最左边补上一个 s[j] ，需要的最少插入次数是 [i, j + 1] 成为回文子串的最少插入次数 + 本次插入，即 dp[i][j] = dp[i][j + 1] + 1 ；

综上所述，状态转移方程为：

当 s[i] == s[j] 时： dp[i][j] = i >= j - 1 ? 1 : dp[i + 1][j - 1] ；
当 s[i] != s[j] 时： dp[i][j] = min(dp[i + 1][j], dp[i][j - 1]) + 1；

返回值：根据「状态表示」，我们需要返回 [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));
		
		        //  dp[i][j] 表⽰字符串 [i, j] 区域成为回⽂⼦串的最少插⼊次数
		        
		        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(1 + dp[i + 1][j], 1 + 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
17
18
19
20
21
22

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/Monodyee/article/detail/502535