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

2024-01-06 08:36

本文主要是介绍【动态规划】【字符串】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;
};

扩展阅读

视频课程

有效学习:明确的目标 及时的反馈 拉伸区(难度合适),可以先学简单的课程,请移步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的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/575796

相关文章

C#数据结构之字符串(string)详解

《C#数据结构之字符串(string)详解》:本文主要介绍C#数据结构之字符串(string),具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录转义字符序列字符串的创建字符串的声明null字符串与空字符串重复单字符字符串的构造字符串的属性和常用方法属性常用方法总结摘

C#如何动态创建Label,及动态label事件

《C#如何动态创建Label,及动态label事件》:本文主要介绍C#如何动态创建Label,及动态label事件,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录C#如何动态创建Label,及动态label事件第一点:switch中的生成我们的label事件接着,

SpringCloud动态配置注解@RefreshScope与@Component的深度解析

《SpringCloud动态配置注解@RefreshScope与@Component的深度解析》在现代微服务架构中,动态配置管理是一个关键需求,本文将为大家介绍SpringCloud中相关的注解@Re... 目录引言1. @RefreshScope 的作用与原理1.1 什么是 @RefreshScope1.

MyBatis 动态 SQL 优化之标签的实战与技巧(常见用法)

《MyBatis动态SQL优化之标签的实战与技巧(常见用法)》本文通过详细的示例和实际应用场景,介绍了如何有效利用这些标签来优化MyBatis配置,提升开发效率,确保SQL的高效执行和安全性,感... 目录动态SQL详解一、动态SQL的核心概念1.1 什么是动态SQL?1.2 动态SQL的优点1.3 动态S

Java实现时间与字符串互相转换详解

《Java实现时间与字符串互相转换详解》这篇文章主要为大家详细介绍了Java中实现时间与字符串互相转换的相关方法,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录一、日期格式化为字符串(一)使用预定义格式(二)自定义格式二、字符串解析为日期(一)解析ISO格式字符串(二)解析自定义

python中字符串拼接的几种方法及优缺点对比详解

《python中字符串拼接的几种方法及优缺点对比详解》在Python中,字符串拼接是常见的操作,Python提供了多种方法来拼接字符串,每种方法有其优缺点和适用场景,以下是几种常见的字符串拼接方法,需... 目录1. 使用 + 运算符示例:优缺点:2. 使用&nbsjsp;join() 方法示例:优缺点:3

java字符串数字补齐位数详解

《java字符串数字补齐位数详解》:本文主要介绍java字符串数字补齐位数,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录Java字符串数字补齐位数一、使用String.format()方法二、Apache Commons Lang库方法三、Java 11+的St

C++字符串提取和分割的多种方法

《C++字符串提取和分割的多种方法》在C++编程中,字符串处理是一个常见的任务,尤其是在需要从字符串中提取特定数据时,本文将详细探讨如何使用C++标准库中的工具来提取和分割字符串,并分析不同方法的适用... 目录1. 字符串提取的基本方法1.1 使用 std::istringstream 和 >> 操作符示

C语言字符函数和字符串函数示例详解

《C语言字符函数和字符串函数示例详解》本文详细介绍了C语言中字符分类函数、字符转换函数及字符串操作函数的使用方法,并通过示例代码展示了如何实现这些功能,通过这些内容,读者可以深入理解并掌握C语言中的字... 目录一、字符分类函数二、字符转换函数三、strlen的使用和模拟实现3.1strlen函数3.2st

mybatis-plus 实现查询表名动态修改的示例代码

《mybatis-plus实现查询表名动态修改的示例代码》通过MyBatis-Plus实现表名的动态替换,根据配置或入参选择不同的表,本文主要介绍了mybatis-plus实现查询表名动态修改的示... 目录实现数据库初始化依赖包配置读取类设置 myBATis-plus 插件测试通过 mybatis-plu