[LeetCode] 1278. Palindrome Partitioning III 拆分回文串之三

You are given a string s containing lowercase letters and an integer k. You need to :

  • First, change some characters of s to other lowercase English letters.
  • Then divide s into k non-empty disjoint substrings such that each substring is a palindrome.

Return the minimal number of characters that you need to change to divide the string.

Example 1:

Input: s = "abc", k = 2 Output: 1 Explanation: You can split the string into "ab" and "c", and change 1 character in "ab" to make it palindrome. 

Example 2:

Input: s = "aabbc", k = 3 Output: 0 Explanation: You can split the string into "aa", "bb" and "c", all of them are palindrome. 

Example 3:

Input: s = "leetcode", k = 8 Output: 0 

Constraints:

  • 1 <= k <= s.length <= 100.
  • s only contains lowercase English letters.

这道题是拆分回文串系列的第三道,之前的两道分别是 Palindrome Partitioning IIPalindrome Partitioning,相对于前两道题来说,这道题更加的复杂一些,这里给了一个只有小写字母的字符串s和一个正整数k,说是首先改变s中的一些字母,然后将s分割为k个回文串,问最少需要改变多少个字母。再来分析一下题目中给的例子,比如例子1,可以先将字符串 abc 分割成 aac 或者 bbc,然后再分割成两个回文串。例子2给的 aabbc 可以直接分割成三个回文串,并不需要改变字母。例子3正好有八个字母,可以直接拆分为8个回文串,从而并不需要改变字母。所以这道题实际上就是两个部分,如何确定要修改哪些字母,和如何拆分为k个回文串。这两个部分实际上是相辅相成的,假如先不考虑修改字母,而是将字符串s分割成任意的k个子串,然后计算将每个子串变为回文串需要改变的字母个数,全部加起来就是一个解(但不一定是最优解),只有计算出所有的分割的方式,找到其中的最小值,才是本题需要的解。当将字符串分割成k个子串时,需要知道每个子串变为回文串的字母改变个数,由于分割成的子串可能之前也出现过,所以每次都计算一遍如何变为子串,就非常的不高效,可能存在重复计算,最好是能提前计算出每个子串变成回文串的 cost,这样之后需要哪个就直接取就行了,就像建立累加和数组一样,可以快速得到任意子数组的数字之和。

这里使用一个二维数组 pd,其中 pd[i][j] 表示范围为 [i, j] 的子串变为回文串需要改变的字母的个数,计算方法也比较简单,将其放到一个子函数 getChanges 中来处理,用两个指针 start 和 end 来指向子串的首尾位置,然后比较对应位置的字母是否相等,不相等的话结果 res 自增1即可。更新完了 pd 数组之后,就可以将子串s分割成任意的k个子串了,这里使用一个 dp 数组,其中 dp[i][j] 表示范围是 [0, j] 的子串分割为i个回文串所需的最小的字母改变个数。现在来看状态转移方程怎么写,首先分割为1个回文串的情况就是字符串s本身,只要知道其需要改变多少个字母变为回文串即可,这个可以在 pd 数组直接查到,所以 dp[1][j] 可以用 pd[0][j] 来初始化更新。然后就是更新分割数为2到k的情况,既然要更新分割为i个的 dp 值,那么至少要包括两个数字,所以 end 的范围是 [i-1, n-1],然后就要尝试替换最后一个分割出的回文串的各种情况,起始位置 start 的范围是 [i-2, end-1],则 dp[i][end] 可以用 dp[i-1][start] + pd[start+1][end] 来更新,因为范围 [0, start] 里分割了 i-1 个回文串,剩下的 [start+1, end] 范围内是另一个回文串。最终的结果就保存到了 dp[k][n-1] 中了,参见代码如下:

class Solution { public:     int palindromePartition(string s, int k) {         int n = s.size();         vector<vector<int>> pd(n, vector<int>(n)), dp(k + 1, vector<int>(n));         for (int i = n - 1; i >= 0; --i) {             for (int j = i + 1; j < n; ++j) {                 pd[i][j] = getChanges(s, i, j);             }         }         for (int i = 0; i < n; ++i) {             dp[1][i] = pd[0][i];         }         for (int i = 2; i <= k; ++i) {             for (int end = i - 1; end < n; ++end) {                 dp[i][end] = n;                 for (int start = end - 1; start >= i - 2; --start) {                     dp[i][end] = min(dp[i][end], dp[i - 1][start] + pd[start + 1][end]);                 }             }         }         return dp[k][n - 1];     }     int getChanges(string s, int start, int end) {         int res = 0;         while (start < end) {             if (s[start++] != s[end--]) ++res;         }         return res;     } }; 

Github 同步地址:

https://github.com/grandyang/leetcode/issues/CHANGE_ME

类似题目:

Palindrome Partitioning IV

Palindrome Partitioning II

Palindrome Partitioning

参考资料:

https://leetcode.com/problems/palindrome-partitioning-iii/

https://leetcode.com/problems/palindrome-partitioning-iii/discuss/498677/Step-by-Step-solution-DP-(Java)

https://leetcode.com/problems/palindrome-partitioning-iii/discuss/442083/Simple-C%2B%2B-Dp-O(N2K)-Beats-100-with-Explanation

LeetCode All in One 题目讲解汇总(持续更新中...)

推荐这些技术文章:

[LeetCode] 1278. Palindrome Partitioning III 拆分回文串之三

You are given a string s containing lowercase letters and an integer k. You need to :

First, change some characters of s to other lowercase English letters.
Then divide&nbs...

LeetCode 每日一题(5. 最长回文子串)

 

class Solution {
public:
string longestPalindrome(string s) {
if (s.size() <= 1){
return s;
}

int a = 0; //记录临时值
int length = 0;

...

LeetCode-516. 最长回文子序列

题目来源
516. 最长回文子序列
题目详情
给你一个字符串 s ,找出其中最长的回文子序列,并返回该序列的长度。
子序列定义为:不改变剩余字符顺序的情况下,删除某些字符或者不删除任何字符形成的一个序列。
示例 1:
输入: s = "bbbab"
输出: 4
解释: 一个可能的最长回文子序列为 "bbbb" 。
示例 2:
输入: s = "cbbd"
输出: 2
解释: 一个可能的最长回文子...

LeetCode-125. 验证回文串

题目来源
125. 验证回文串
题目详情
给定一个字符串,验证它是否是回文串,只考虑字母和数字字符,可以忽略字母的大小写。
说明: 本题中,我们将空字符串定义为有效的回文串。
示例 1:
输入: "A man, a plan, a canal: Panama"
输出: true
解释: "amanaplanacanalpanama" 是回文串
示例 2:
输入: "race a car"
输出:...

LeetCode/最长回文子串

描述
对于长度为n的一个字符串A(仅包含数字,大小写英文字母),请设计一个高效算法,计算其中最长回文子串的长度。
思路
1.暴力列举所有串,判断串是否为回文串并将当下最长的进行存储
2.中心扩散,顺序遍历,对每个点进行左右同时扩散,得到其中心点对应的最大回文串和回文串长度(考虑奇偶串要分别用一个中心和两个中心点进行遍历),时间复杂度为O(n2),空间复杂度为O(1)
3.动态规划,用二维dp数组...

【LeetCode】647. 回文子串 [C++]

【题目描述】
给你一个字符串 s ,请你统计并返回这个字符串中 回文子串 的数目。
回文字符串 是正着读和倒过来读一样的字符串。
子字符串 是字符串中的由连续字符组成的一个序列。
具有不同开始位置或结束位置的子串,即使是由相同的字符组成,也会被视作不同的子串。
 
【思路】
计算有多少个回文子串的最朴素方法就是枚举出所有的回文子串,而枚举出所有的回文字串又有两种思路,分别是:
1.枚举...

LeetCode No5 最长回文子串

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

示例 1:
输入:s = "babad"
输出:"bab"
解释:"aba" 同样是符合题意的答案。
示例 2:
输入:s = "cbbd"
输出:"bb"
提示:
1 <= s.length <= 1000
s 仅由数字和英文字母组成
解题思路
中心扩展法
首先要知道回文串的定义,回文串是一个正读和反读都一样的字符串,比如 ...

5 最长回文子串(LeetCode HOT 100)

描述:
给你一个字符串 s,找到 s 中最长的回文子串。
示例 1:
输入:s = "babad"
输出:"bab"
解释:"aba" 同样是符合题意的答案。

示例 2:
输入:s = "cbbd"
输出:"bb"

提示:

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

Soulution:
public String longestPalindrom...

分割/拆分字符串的方法

1.substr
substr(start,length)表示从start位置开始,截取length长度的字符串。

var src="https://www.cnblogs.com/linhan8888/p/images/off_1.png";
alert(src.substr(7,3));

弹出值为:off

2.substring
substring(start,end)表示从start...

LeetCode 解题目录汇总

LeetCode 目录汇总
LeetCode 36. 有效的数独
LeetCode 138 复制带随机指针的链表
LeetCode 160 相交链表
LeetCode 166 Excel表列名称
LeetCode 219 存在重复元素 II
LeetCode 223 矩形面积
LeetCode 275 H 指数II
LeetCode 299 猜数字游戏
LeetCode 313 超级丑数
Lee...

[LeetCode] 1234. Replace the Substring for Balanced String 替换子串得到平衡字符串

You are given a string containing only 4 kinds of characters 'Q', 'W', 'E' and 'R'.
A string is said to be balancedif each of its characters appears n/4 times...

cf607 B. Zuma(区间dp,回文串)

题意:
给定数组,每次可以删除一个回文子段,求最少几次可以删完。
\(1\le n \le 500\)
思路:
\(f(l,r)\) 表示删除 \([l,r]\) 需要的最小次数。如果 \(a_l=a_r\),那么 \(a_l\) 和 \(a_r\) 可以接到 \([l+1,r-1]\) 中的某个回文序列中,不需要额外代价。
特殊处理长度为2的子段
const int N = 505;
int ...

线性DP 之划分成回文字符串 题解

一:
问题描述:
当一个字符串正序和反序是完全相同时,我们称之为“回文串”。例如“racecar”就是一个回文串,而“fastcar”就不是。现在给一个字符串s,把它分割成若干个互不相交的回文子串,求分割的回文子串的最少个数。
输入格式:
第一行为正整数t(≤10),表示数据组数;接下来t行,每行一个完全由小写字母组成的字符串,长度不超过1000。
输出格式:
对于每组数据,输出最少回文子串数。...

leetcode(8)回文系列题目

动态规划:
(1)647. 回文子串
布尔类型的dp[i][j]:表示区间范围[i,j] (注意是左闭右闭)的子串是否是回文子串,如果是dp[i][j]为true,否则为false。

当s[i]与s[j]不相等,dp[i][j]一定是false。
当s[i]与s[j]相等时,有如下三种情况

情况一:下标i 与 j相同,同一个字符例如a,当然是回文子串
情况二:下标i 与 j相差为1,例如aa...

codeforces 1140E Palindrome-less Arrays

题目链接:http://codeforces.com/contest/1140/problem/E
 
题目大意:
如果一个数组的存在一个奇数长的回文就不好。
不是不好的数组是好的。
你可以把-1用1到k中一个数替换。问可以有多少种不同的好数组。
 
开虚拟赛最后一分钟把它A了,很开心,很开心。
 
思路:
我们翻译一下,如果存在长度为5的回文就必须会出现长度为3的...

文章标题:[LeetCode] 1278. Palindrome Partitioning III 拆分回文串之三
文章链接:https://www.dianjilingqu.com/3655.html
本文章来源于网络,版权归原作者所有,如果本站文章侵犯了您的权益,请联系我们删除,联系邮箱:saisai#email.cn,感谢支持理解。
THE END
< <上一篇
下一篇>>