分割回文串-ii

[编程题]分割回文串-ii

热度指数：36989 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

给出一个字符串s，分割s使得分割出的每一个子串都是回文串

计算将字符串s分割成回文分割结果的最小切割数

例如:给定字符串s="aab",

返回1，因为回文分割结果["aa","b"]是切割一次生成的。

示例1

输入

"aab"

输出

算法知识视频讲解

华科不平凡

发表于 2020-08-24 22:09:40

典型的动态规划问题：对于每个位置i，以递增的方式找长度为1,3,5,7...的回文子串，然后找长度为2,4,6,8的回文子串；假设回文子串的起始位置为idx_s，结束位置为idx_e，更新dp数组的公式为dp[idx_e] = min(dp[idx_s-1] + 1, dp[idx_e]) 考展开全文

ls.joshua

发表于 2020-04-20 22:32:57

DP动态规划解法,时间复杂度为 O(1/4 N^3);定义：dp[i][j]表示字符串 i -> j切分成回文的答案数，状态转移方程为：dp[i][j] = min(dp[i][t]+[t+1][j]),其中t位于区间[i, j];求解过程：求解的方向，需要先求解出左下角的子三角形的解，才能求展开全文

喝醉了Ta的梦,晚安

发表于 2022-01-05 10:25:20

这里用了dp数组记录最小值,第一位dp[0]=-1,目的很简单,当j=0,整体是回文串时, 代码可以复用,-1+1=0; 也可以用递归的方法 public: /** * * @param s string字符串 * @return int整型 */ bool isPalindr 展开全文

郑州大学

发表于 2023-05-10 15:06:10

import java.util.*; public class Solution { /** * 解法一 * 时间复杂度: O(N^3) * 空间复杂度: O(N) * 以下以 [x,y] 表示 s 的第 x 个字符到第 y 个字符的字串展开全文

新时代——农民工

发表于 2023-03-13 19:50:24

import java.util.*; /** * 思路: 动态规划 * 问题: 求将s分割为每一段都是回文串的的最小分割数 * 子问题: 将s的一部分分割为回文串的次数 * 状态: 将s的前i个字符分割为回文串的最小次数 * 分析: 举例 aab, 初始状态1个字符的时展开全文

牛客Yhq

发表于 2023-03-20 15:43:12

// 状态：F(i)前i个字符的最小切割数 // 转移方程：如果当前整体是回文串：F(i)=0 // 整体不是：F(i)=min(F(j)+1) // 前提：j<i并且[j+1,i]是回文串 // 初始值：F(i)=i-1(最大分割数：字符个展开全文

哈哈哈哈鹅

发表于 2021-11-15 21:23:16

//时间复杂度O（n^3) public class PalindromeString { //判断回文串 public static boolean&n 展开全文

哈哈哈哈鹅

发表于 2021-11-15 21:26:48

//这是对前面回文串分割的优化算法，这个时间复杂度是O(n^2) // 方法是计算最小分割次数时，不用再去遍历字符串判断是否回文，而是先将字符串是否回文的结果保存下来，用一个二维数组来保存，i表示开始字符，j表示结束字符 //判断字符串是否回文就变成了求（i,j)区间是否是回文字符串，因此也可以用动展开全文

哈哈哈哈鹅

发表于 2021-11-15 21:29:15