作者推荐
本文涉及知识点
LeetCode1278分割回文串 III
给你一个由小写字母组成的字符串 s，和一个整数 k。
请你按下面的要求分割字符串：
首先，你可以将 s 中的部分字符修改为其他的小写英文字母。
接着，你需要把 s 分割成 k 个非空且不相交的子串，并且每个子串都是回文串。
请返回以这种方式分割字符串所需修改的最少字符数。
示例 1：
输入：s = “abc”, k = 2
输出：1
解释：你可以把字符串分割成 “ab” 和 “c”，并修改 “ab” 中的 1 个字符，将它变成回文串。
示例 2：
输入：s = “aabbc”, k = 3
输出：0
解释：你可以把字符串分割成 “aa”、“bb” 和 “c”，它们都是回文串。
示例 3：
输入：s = “leetcode”, k = 8
输出：0
提示：
1 <= k <= s.length <= 100
s 中只含有小写英文字母。
动态规划
预处理
vNeedChange[i][j]表示将s[i,j]变成回文需要改变的字符数。 枚举中心和长度,时间复杂度:O(nn)。奇数长度回文和偶数长度回文，分别枚举。
动态规划的状态表示
pre[j] 表示s[0,j) 是由iK个回文串组成，最少改变的字符数。
动态规划的转移方程
dp[i]= M i n j = 0 i − 1 Min\Large_{j=0}^{i-1}Minj=0i−1(pre[j]+vNeedChange[j][i-1]) 状态数:n，故空间复杂度：O(n)。转移每个状态的时间复杂度：O(n)，故总时间复杂度：O(nn)。
动态规划的初始状态
全为0。
动态规划的填表顺序
i从1到s.length
动态规划的返回值
dp.back()
代码
核心代码
class Solution { public: int palindromePartition(string s, int k) { m_c = s.length(); vector<vector<int>> vNeedChange(m_c, vector<int>(m_c)); for (int i = 0; i < m_c; i++) { int iNotSame = 0; for (int l = i, r = i; (l >= 0) && (r < m_c); l--,r++) { iNotSame += (s[l] != s[r]); vNeedChange[l][r] = iNotSame; } } for (int i = 0; i < m_c; i++) { int iNotSame = 0; for (int l = i, r = i+1; (l >= 0) && (r < m_c); l--, r++) { iNotSame += (s[l] != s[r]); vNeedChange[l][r] = iNotSame; } } vector<int> pre(m_c + 1, 1000); pre[0] = 0; while (k--) { vector<int> dp(m_c + 1, 1000); for (int i = 1; i <= m_c; i++) { for (int j = 0; j < i; j++) { dp[i] = min(dp[i], pre[j] + vNeedChange[j][i - 1]); } } pre.swap(dp); } return pre.back(); } 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 ; int k = 0; { Solution sln; s = "abc", k = 2; auto res = sln.palindromePartition(s, k); Assert(1, res); } { Solution sln; s = "aabbc", k = 3; auto res = sln.palindromePartition(s, k); Assert(0, res); } { Solution sln; s = "leetcode", k = 8; auto res = sln.palindromePartition(s, k); Assert(0, res); } }
2023年一月版
class Solution {
public:
int palindromePartition(string s, int k) {
vector<vector> vBeginEndNeedNum(s.length(), vector(s.length(),1000));
//vBeginEndNeedNum[i][j] s[i]到s[j]变成回文改变的次数
for (int i = 0; i < s.length(); i++)
{
{//处理奇数回文
int iNeedChange = 0;
vBeginEndNeedNum[i][i] = 0;
for (int len = 1;; len++)
{
const int iBegin = i - len;
const int iEnd = i + len;
if (iBegin < 0)
{
break;
}
if (iEnd >= s.length())
{
break;
}
if (s[iBegin] != s[iEnd])
{
iNeedChange++;
}
vBeginEndNeedNum[iBegin][iEnd] = iNeedChange;
}
}
{//处理偶数回文
int iNeedChange = 0;
for (int len = 1;; len++)
{
const int iBegin = i - len + 1;
const int iEnd = i + len;
if (iBegin < 0)
{
break;
}
if (iEnd >= s.length())
{
break;
}
if (s[iBegin] != s[iEnd])
{
iNeedChange++;
}
vBeginEndNeedNum[iBegin][iEnd] = iNeedChange;
}
}
}
vector pre = vBeginEndNeedNum[0];
for (int iSetp = 0; iSetp + 1 < k; iSetp++)
{
vector dp(s.length(),1000);
dp[0] = pre[0];
for (int i = iSetp+1; i < s.length(); i++)
{
for (int j = iSetp ; j < i; j++)
{
dp[i] = min(dp[i], pre[j] + vBeginEndNeedNum[j + 1][i]);
}
}
pre.swap(dp);
}
return pre[s.length() - 1];
}
};
