蚌埠网站建设文章,代做网站公司哪家好,求会wordpress的人,一个完整网站制作的实例在本篇博客中将介绍分割回文串Ⅱ以及分割回文串Ⅳ这两个题目。 分割回文串Ⅱ
题目描述
给你一个字符串 s#xff0c;请你将 s 分割成一些子串#xff0c;使每个子串都是回文串。 返回符合要求的 最少分割次数 。
示例#xff1a; 输入#xff1a;s aabac 输… 在本篇博客中将介绍分割回文串Ⅱ以及分割回文串Ⅳ这两个题目。 分割回文串Ⅱ
题目描述
给你一个字符串 s请你将 s 分割成一些子串使每个子串都是回文串。 返回符合要求的 最少分割次数 。
示例 输入s aabac 输出2 解释只需2次分割就可将 s 分割成 [a,aba,c] 这样3个回文子串。 解题思路
为了解决这个问题我们可以使用动态规划Dynamic Programming, DP的方法。具体来说我们可以先计算出字符串 s 中所有子串是否是回文串并存储这个结果以便后续使用。然后我们再次使用动态规划来找出将字符串 s 分割成回文子串所需的最少分割次数。
第一步判断子串是否为回文
我们定义一个二维数组 dp1[i][j]其中 dp1[i][j] 表示从索引 i 到索引 j 的子串 s[i...j] 是否是回文串。我们可以从字符串的两端向中间遍历并更新这个数组(这部分与此前回文子串一题中相同 动态规划-回文子串-CSDN博客)。
第二步动态规划求解最少分割次数
这一步的动态规划思路主要是基于已经判断好的回文子串信息来求解将整个字符串 s 分割成多个回文子串所需的最少分割次数。这里的关键在于利用动态规划来避免重复计算并逐步构建出整个问题的解。
定义状态 定义 dp2[i] 表示将字符串 s 的前 i1 个字符即 s[0...i]分割成多个回文子串所需的最少分割次数。初始化 dp2[0] 初始化为 0因为空字符串不需要分割。状态转移 对于每个位置 i从 1 到 n-1其中 n 是字符串 s 的长度我们需要找到所有可能的分割点 j从 0 到 i-1使得 s[j1...i] 是一个回文串。这可以通过查询之前计算好的 dp1 数组来实现其中 dp1[j1][i] 表示 s[j1...i] 是否为回文串。如果找到了这样的 j那么我们可以将 s[0...i] 分割为 s[0...j] 和 s[j1...i] 两部分其中 s[j1...i] 已经是一个回文串不需要进一步分割。因此s[0...i] 的最少分割次数就是 s[0...j] 的最少分割次数即 dp2[j]加上 1因为我们在 j 和 i 之间进行了一次分割。我们需要遍历所有可能的 j并更新 dp2[i] 为这些分割方案中的最小值。结果 最终dp2[n-1] 就是整个字符串 s 的最少分割次数。
代码示例
class Solution {
public:int minCut(string s) {int n s.size();vectorvectorbool dp(n, vectorbool(n, false));for (int i 0; i n; i) {dp[i][i] true; // 单个都是回文子串if (i 1 n s[i] s[i 1]) { // 两个相同的字符构成回文子串dp[i][i 1] true;}}for (int len 3; len n; len) { // 从字串长度为3开始遍历for (int i 0; i 1 n - len; i) { // ilen-1nint j i len - 1;if (s[i] s[j] dp[i 1][j - 1] true) {dp[i][j] true;}}}vectorint f(n,INT_MAX); // f[i]: 从0到i 的子串 所符合要求的 最少分割次数f[0] 0;for (int i 1; i n; i) {if (dp[0][i] true) { // 从0到i 的子串是回文串f[i] 0;} else {for (int j 0; j i; j) {if (dp[j][i]) {f[i] min(f[j - 1] 1, f[i]);}}}}return f[n - 1];}
}; 分割回文串Ⅳ
题目描述
给你一个字符串 s 如果可以将它分割成三个 非空 回文子字符串那么返回 true 否则返回 false 。
当一个字符串正着读和反着读是一模一样的就称其为 回文字符串 。
示例 1 输入s abcbdad 输出true 解释abcbdd a bcb dad三个子字符串都是回文的。 示例 2 输入s abaccdef 输出false 解释s 没办法被分割成 3 个回文子字符串。 解题思路
这一题与上题相似要解决这个问题我们可以采用一种比较直观的方法即遍历所有可能的分割点然后检查每个分割点形成的三个子字符串是否都是回文串。为了高效地检查一个子字符串是否是回文串我们可以先预处理一个二维数组或者使用一个函数用于快速判断任意子字符串是否为回文。
第一步初始化动态规划数组
定义一个二维布尔数组dp其中dp[i][j]表示字符串s从索引i到索引j包含两端的子串是否是回文子串。初始化对角线元素dp[i][i]为true因为单个字符自然是回文子串。初始化相邻元素dp[i][i1]为true如果s[i]和s[i1]相等因为两个相同的字符也构成回文子串。
第二步填充动态规划数组
使用两层循环遍历所有可能的子串长度从3开始因为长度为1和2的情况已经在第一步中处理过了和起始位置。对于每个子串检查其首尾字符是否相等并且去掉首尾字符后的子串即dp[i1][j-1]是否是回文子串。如果这两个条件都满足则当前子串是回文子串将dp[i][j]设置为true。
第三步检查是否存在有效的分割
使用两层循环遍历所有可能的分割点第一个和第二个分割点以检查是否存在一种分割方式使得字符串s被分为三个非空回文子串。对于每个分割点组合(i, j)其中i是第一个分割点的位置不包括j是第二个分割点的位置不包括检查dp[0][i-1]、dp[i][j-1]和dp[j][n-1]是否都为true。如果是则表示找到了一个有效的分割方式返回true。如果遍历完所有可能的分割点组合后都没有找到有效的分割方式则返回false。
代码示例
class Solution {
public:bool checkPartitioning(string s) {int n s.size();vectorvectorbool dp(n, vectorbool(n, false));for (int i 0; i n; i) {dp[i][i] true; // 单个都是回文子串if (i 1 n s[i] s[i 1]) { // 两个相同的字符构成回文子串dp[i][i 1] true;}}for (int len 3; len n; len) { // 从字串长度为3开始遍历for (int i 0; i 1 n - len; i) { // ilen-1nint j i len - 1;if (s[i] s[j] dp[i 1][j - 1] true) {dp[i][j] true;}}}for (int i 0; i n - 1; i) {for (int j i 1; j n - 1; j) {if (dp[0][i] dp[i 1][j] dp[j 1][n - 1]) {return true;}}}return false;}
};
