【动态规划】【字符串】132.分割回文串 II

这篇具有很好参考价值的文章主要介绍了【动态规划】【字符串】132.分割回文串 II。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

作者推荐

视频算法专题

本文涉及知识点

动态规划汇总
字符串

LeetCode132. 分割回文串 II

给你一个字符串 s,请你将 s 分割成一些子串,使每个子串都是回文。
返回符合要求的 最少分割次数 。
示例 1:
输入:s = “aab”
输出:1
解释:只需一次分割就可将 s 分割成 [“aa”,“b”] 这样两个回文子串。
示例 2:
输入:s = “a”
输出:0
示例 3:
输入:s = “ab”
输出:1
提示:
1 <= s.length <= 2000
s 仅由小写英文字母组成

动态规划

分两步:
一,枚举回文的中心,记录所有的回文。空间复杂度和时间复杂度都是O(nn)。
二,通过动态规划计算所有所有前缀可以差分成多少个不重叠的子字符串。空间复杂度O(n),时间复杂度是O(nn)。

变量解析

vRightToLeft(m_c) vRightToLeft[i] 包括元素j,表示s[i,j],是回文串。 vRightToLeft不重复遗漏的记录所有回文串。
dp[i] 记录s[0,i]最少可以划分成多少个不重叠的回文子串

态规范分析

动态规划的状态表示 dp[i]记录s[0,i]最少可以划分成多少个不重叠不遗漏的回文子串
动态规划的转移方程 如果s[left,i]是回文,dp[i]=min(dp[i],dp[left-1]+1)
动态规划的初始状态 全部为INT_MAX
动态规划的填表顺序 i从小到大。由短到长处理子字符串,确保动态规划的无后效性
动态规划的返回值 dp.back()-1

代码

核心代码

class Solution {
public:
	int minCut(string s) {
		m_c = s.length();
		vector<vector<int>> vRightToLeft(m_c);//cRightToLeft[i] 包括元素j,表示s[i,j],是回文串。
		for (int i = 0; i < m_c; i++)
		{
			for (int left = i, right = i; (left >= 0) && (right < m_c)&&(s[left]==s[right]); left--, right++)
			{//奇数长度回文
				vRightToLeft[right].emplace_back(left);
			}
			for (int left = i, right = i+1; (left >= 0) && (right < m_c) && (s[left] == s[right]); left--, right++)
			{//偶数长度回文
				vRightToLeft[right].emplace_back(left);
			}
		}
		vector<int> dp(m_c,INT_MAX);
		for (int i = 0; i < m_c; i++)
		{
			for (const auto& left : vRightToLeft[i])
			{
				dp[i] = min(dp[i], 1 + (left > 0 ? dp[left - 1] : 0));
			}
		}
		return dp.back()-1;
	}
	int m_c;
};

测试用例

template<class T>
void Assert(const T& t1, const T& t2)
{
	assert(t1 == t2);
}

template<class T>
void Assert(const vector<T>& v1, const vector<T>& v2)
{
	if (v1.size() != v2.size())
	{
		assert(false);
		return;
	}
	for (int i = 0; i < v1.size(); i++)
	{
		Assert(v1[i], v2[i]);
	}
}


int main()
{
	string s;	
	{
		Solution sln;
		s = "aab";
		auto res = sln.minCut(s);
		Assert(1, res);
	}
	{
		Solution sln;
		s = "a";
		auto res = sln.minCut(s);
		Assert(0, res);
	}
	{
		Solution sln;
		s = "ab";
		auto res = sln.minCut(s);
		Assert(1, res);
	}
}

2023年1月版

class Solution {
public:
int minCut(string s) {
m_c = s.length();
vector<vector> is;
is.assign(m_c, vector(m_c+1));
for (int c = 0; c < m_c; c++)
{
//长度为1的字符串一定是回文
is[c][1] = true;
}
for (int c = 0; c + 1 < m_c; c++)
{
is[c][2] = (s[c] == s[c + 1]);
}
for (int len = 3; len <= m_c; len++)
{
for (int c = 0; c + len - 1 < m_c; c++)
{
is[c][len] = is[c + 1][len - 2] && (s[c] == s[c + len - 1]);
}
}
//最少多少个回文构成
vector dp(m_c + 1,INT_MAX);
dp[0] = 0;
for (int c = 0; c < m_c; c++)
{
for (int len = 1; len <= m_c; len++)
{
if (is[c][len] && (c+len <= m_c ))
{
dp[c + len] = min(dp[c + len], dp[c] + 1);
}
}
}
return dp[m_c] - 1;
}
int m_c;
};

2023年8月

//马拉车计算回文回文
class CPalindrome
{
public:
//vOddHalfLen[i]表示 以s[i]为中心,且长度为奇数的最长回文的半长,包括s[i]
//比如:“aba” vOddHalfLen[1]为2 “abba” vEvenHalfLen[1]为2
static void Do(vector& vOddHalfLen, vector& vEvenHalfLen,const string& s)
{
vector v;
for (const auto& ch : s)
{
v.emplace_back(ch);
v.emplace_back(‘*’);
}
v.pop_back();
const int len = v.size();
vector vHalfLen(len);
int center = -1, r = -1;
//center是对称中心,r是其右边界(闭)
for (int i = 0; i < len; i++)
{
int tmp = 1;
if (i <= r)
{
int pre = center - (i - center);
tmp = min(vHalfLen[pre], r - i + 1);
}
for (tmp++; (i + tmp - 1 < len) && (i - tmp + 1 >= 0) && (v[i + tmp - 1] == v[i - tmp + 1]); tmp++);
vHalfLen[i] = --tmp;
const int iNewR = i + tmp - 1;
if (iNewR > r)
{
r = iNewR;
center = i;
}
}
vOddHalfLen.resize(s.length());
vEvenHalfLen.resize(s.length());
for (int i = 0; i < len; i++)
{
if (i & 1)
{
vEvenHalfLen[i / 2] = vHalfLen[i] / 2;

		}
		else
		{
			vOddHalfLen[i / 2] = (vHalfLen[i]+1) / 2 ;				
		}
	}
}

};
class Solution {
public:
int minCut(string s) {
m_c = s.length();
vector vOddHalfLen, vEvenHalfLen;
CPalindrome::Do(vOddHalfLen, vEvenHalfLen,s);
//邻接表
vector<vector> vNeiBo(m_c+1);
for (int i = 0; i < m_c; i++)
{
for (int len = 1; len <= vOddHalfLen[i]; len++)
{
const int cur = i - len + 1;
const int next = i + len;
vNeiBo[cur].emplace_back(next);
}
for (int len = 1; len <= vEvenHalfLen[i]; len++)
{
const int cur = i - len + 1;
const int next = i + len+1;
vNeiBo[cur].emplace_back(next);
}
}
queue que;
que.emplace(0);
vector vDis(m_c+1, -1);
vDis[0] = 0;
while (que.size())
{
const int cur = que.front();
que.pop();
const int curDis = vDis[cur];
for (const auto& next : vNeiBo[cur])
{
if (-1 != vDis[next])
{
continue;
}
vDis[next] = curDis + 1;
que.emplace(next);
}
}
return vDis.back() - 1;
}
int m_c;
};

【动态规划】【字符串】132.分割回文串 II,# 算法题,动态规划,算法,c++,leetcode,字符串,回文,马拉车

扩展阅读

视频课程

有效学习:明确的目标 及时的反馈 拉伸区(难度合适),可以先学简单的课程,请移步CSDN学院,听白银讲师(也就是鄙人)的讲解。
https://edu.csdn.net/course/detail/38771

如何你想快

速形成战斗了,为老板分忧,请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176

相关下载

想高屋建瓴的学习算法,请下载《喜缺全书算法册》doc版
https://download.csdn.net/download/he_zhidan/88348653

我想对大家说的话
闻缺陷则喜是一个美好的愿望,早发现问题,早修改问题,给老板节约钱。
子墨子言之:事无终始,无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙,那算法就是他的是睛

测试环境

操作系统:win7 开发环境: VS2019 C++17
或者 操作系统:win10 开发环境: VS2022 C++17
如无特殊说明,本算法用**C++**实现。

【动态规划】【字符串】132.分割回文串 II,# 算法题,动态规划,算法,c++,leetcode,字符串,回文,马拉车文章来源地址https://www.toymoban.com/news/detail-779368.html

到了这里,关于【动态规划】【字符串】132.分割回文串 II的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【算法|动态规划No.28】leetcode1312. 让字符串成为回文串的最少插入次数

    个人主页:兜里有颗棉花糖 欢迎 点赞👍 收藏✨ 留言✉ 加关注💓本文由 兜里有颗棉花糖 原创 收录于专栏【手撕算法系列专栏】【LeetCode】 🍔本专栏旨在提高自己算法能力的同时,记录一下自己的学习过程,希望对大家有所帮助 🍓希望我们一起努力、成长,共同进步。

    2024年02月06日
    浏览(55)
  • Leetcode 第 108 场双周赛 Problem C 将字符串分割为最少的美丽子字符串(动态规划)

    Leetcode 第 108 场双周赛 Problem C 将字符串分割为最少的美丽子字符串(动态规划) 题目 给你一个二进制字符串 s ,你需要将字符串分割成一个或者多个 子字符串 ,使每个子字符串都是 美丽 的。 如果一个字符串满足以下条件,我们称它是 美丽 的: 它不包含前导 0 。 它是

    2024年02月15日
    浏览(43)
  • 动态规划-分割回文串 II

    跟着九章侯老师学习了动态规划专题之后根据学习所总结: 给你一个字符串 s,请你将 s 分割成一些子串,使每个子串都是回文。 返回符合要求的 最少分割次数 。 输入:s = “aab” 输出:1 解释:只需一次分割就可将 s 分割成 [“aa”,“b”] 这样两个回文子串。 输入:s = “

    2024年02月10日
    浏览(45)
  • 动态规划(一) 变态青蛙跳台阶、最大连续子数组和、字符串分割 附源码讲解

    实现 import java.util.*; public class Main { public static void main(String[] args) { Scanner scan = new Scanner(System.in); while (scan.hasNext()){ int length = scan.nextInt(); int[] array = new int[length]; for (int i = 0; i length; i++) { array[i] = scan.nextInt(); } System.out.println(findResult(array)); } } private static int findResult(int[] array) {

    2024年04月17日
    浏览(52)
  • c++:string相关的oj题(415. 字符串相加、125. 验证回文串、541. 反转字符串 II、557. 反转字符串中的单词 III)

    传送门 首先,定义两个指针 index1 和 index2 分别指向两个输入字符串的最后一位,用来从后往前遍历字符串。 然后定义一个变量 next 用来表示进位,初始化为 0。 接下来使用一个循环来遍历两个字符串,直到 index1 和 index2 都小于 0。在循环中,每次取出 index1 和 index2 对应位置

    2024年01月23日
    浏览(55)
  • 【动态规划】【字符串】扰乱字符串

    视频算法专题 动态规划汇总 字符串 使用下面描述的算法可以扰乱字符串 s 得到字符串 t : 如果字符串的长度为 1 ,算法停止 如果字符串的长度 1 ,执行下述步骤: 在一个随机下标处将字符串分割成两个非空的子字符串。即,如果已知字符串 s ,则可以将其分成两个子字符

    2024年02月03日
    浏览(58)
  • 【学会动态规划】环绕字符串中唯一的子字符串(25)

    目录 动态规划怎么学? 1. 题目解析 2. 算法原理 1. 状态表示 2. 状态转移方程 3. 初始化 4. 填表顺序 5. 返回值 3. 代码编写 写在最后: 学习一个算法没有捷径,更何况是学习动态规划, 跟我一起刷动态规划算法题,一起学会动态规划! 题目链接:467. 环绕字符串中唯一的子字

    2024年02月10日
    浏览(36)
  • 动态规划--通配字符串匹配

    1. 题目来源 链接:通配符匹配 来源:LeetCode 2. 题目说明 给定一个字符串 (s) 和一个字符模式 § ,实现一个支持 ‘?’ 和 ‘*’ 的通配符匹配。 ‘?’ 可以匹配任何单个字符。 ‘*’ 可以匹配任意字符串(包括空字符串)。 两个字符串完全匹配才算匹配成功。 说明: s 可能为

    2024年02月14日
    浏览(48)
  • 【面试经典150 | 动态规划】交错字符串

    本专栏专注于分析与讲解【面试经典150】算法,两到三天更新一篇文章,欢迎催更…… 专栏内容以分析题目为主,并附带一些对于本题涉及到的数据结构等内容进行回顾与总结,文章结构大致如下,部分内容会有增删: Tag:介绍本题牵涉到的知识点、数据结构; 题目来源:

    2024年04月15日
    浏览(63)
  • 有效的括号字符串(力扣)动态规划、贪心 JAVA

    给你一个只包含三种字符的字符串,支持的字符类型分别是 ‘(’、‘)’ 和 ‘*’。请你检验这个字符串是否为有效字符串,如果是有效字符串返回true 。 有效字符串符合如下规则: 任何左括号 ‘(’ 必须有相应的右括号 ‘)’。 任何右括号 ‘)’ 必须有相应的左括号 ‘(’

    2024年02月14日
    浏览(38)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包