题目
给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是回文。
返回符合要求的 最少分割次数 。
示例 1：
输入：s = “aab”
输出：1
解释：只需一次分割就可将 s 分割成 [“aa”,“b”] 这样两个回文子串。
示例 2：
输入：s = “a”
输出：0
示例 3：
输入：s = “ab”
输出：1
提示：
1 <= s.length <= 2000
s 仅由小写英文字母组成
2023年1月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<int> 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<int> 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<int> que; que.emplace(0); vector<int> 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;
};
其它
视频课程
如果你觉得复杂，想从简单的算法开始，可以学习我的视频课程。
https://edu.csdn.net/course/detail/38771
我的其它课程
https://edu.csdn.net/lecturer/6176
测试环境
win7 VS2019 C++17
相关下载
doc版文档，排版好
https://download.csdn.net/download/he_zhidan/88348653
