作者推荐
视频算法专题
本文涉及知识点
动态规划汇总 字符串
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
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
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
void Assert(const T& t1, const T& t2)
{
assert(t1 == t2);
}
template
void Assert(const vector
{
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
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
扩展阅读
视频课程
有效学习:明确的目标 及时的反馈 拉伸区(难度合适),可以先学简单的课程,请移步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++**实现。
参考文章
发表评论