【动态规划】【回文】【字符串】1278分割回文串 III

作者推荐

【动态规划】【前缀和】【C++算法】LCP 57. 打地鼠

本文涉及知识点

动态规划汇总

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];

}

};