首页 > 试题广场 >

分割回文串-ii

[编程题]分割回文串-ii
  • 热度指数：37049 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
  • 算法知识视频讲解
给出一个字符串s，分割s使得分割出的每一个子串都是回文串
计算将字符串s分割成回文分割结果的最小切割数
例如:给定字符串s="aab",
返回1，因为回文分割结果["aa","b"]是切割一次生成的。
示例1

输入

"aab"

输出

1
算法知识视频讲解
开通博客
头像 华科不平凡
发表于 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]) 考 展开全文
去ta的博客 赞 (2) 回复(0) 收起
头像 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的博客 赞 (1) 回复(0) 收起
头像 喝醉了Ta的梦,晚安
发表于 2022-01-05 10:25:20
这里用了dp数组记录最小值,第一位dp[0]=-1,目的很简单,当j=0,整体是回文串时, 代码可以复用,-1+1=0; 也可以用递归的方法 public: /** * * @param s string字符串 * @return int整型 */ bool isPalindr 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 郑州大学
发表于 2023-05-10 15:06:10
import java.util.*; public class Solution { /** * 解法一 * 时间复杂度: O(N^3) * 空间复杂度: O(N) * 以下以 [x,y] 表示 s 的第 x 个字符到第 y 个字符的字串 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 新时代——农民工
发表于 2023-03-13 19:50:24
import java.util.*; /** * 思路: 动态规划 * 问题: 求将s分割为每一段都是回文串的的最小分割数 * 子问题: 将s的一部分分割为回文串的次数 * 状态: 将s的前i个字符分割为回文串的最小次数 * 分析: 举例 aab, 初始状态1个字符的时 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 牛客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(最大分割数：字符个 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 哈哈哈哈鹅
发表于 2021-11-15 21:23:16
//时间复杂度O（n^3) public class PalindromeString {     //判断回文串     public static boolean&n 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 哈哈哈哈鹅
发表于 2021-11-15 21:26:48
//这是对前面回文串分割的优化算法，这个时间复杂度是O(n^2) // 方法是计算最小分割次数时，不用再去遍历字符串判断是否回文，而是先将字符串是否回文的结果保存下来，用一个二维数组来保存，i表示开始字符，j表示结束字符 //判断字符串是否回文就变成了求（i,j)区间是否是回文字符串，因此也可以用动 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 哈哈哈哈鹅
发表于 2021-11-15 21:29:15
//这是对前面回文串分割的优化算法，这个时间复杂度是O(n^2) // 方法是计算最小分割次数时，不用再去遍历字符串判断是否回文，而是先将字符串是否回文的结果保存下来，用一个二维数组来保存，i表示开始字符，j表示结束字符 //判断字符串是否回文就变成了求（i,j)区间是否是回文字符串，因此也可以用动 展开全文
去ta的博客 赞 (0) 回复(0) 收起

问题信息

动态规划
难度：
114条回答 32942浏览

热门推荐

通过挑战的用户

查看代码

相关试题

分割回文串-ii

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号