C ++中的回文分割III

  • Z时代
  • 2024-01-10
  • 分类：综合

假设我们有一个包含小写字母和整数k的字符串s。我们必须维护一些属性。这些是-

  • 首先，我们必须将s的某些字符（如果需要）更改为其他小写英文字母。

  • 然后将字符串s分为k个子字符串，以使每个子字符串都是回文。

我们必须找到为分割字符串而需要更改的最少字符数。

因此，如果字符串像“ ababbc”并且k = 2，则答案将是1，因为我们必须更改一个字符以将其分成两个回文字符串。因此，如果将c更改为b，或将倒数第二个b更改为c，则可以得到一个回文，如“ bbb”或“ cbc”，而另一个回文为“ aba”。

为了解决这个问题，我们将遵循以下步骤-

  • 定义大小为105 x 105的数组备忘。

  • 定义一个函数solve()，它将使用s，idx，k，一个2D数组> dp，

  • 如果idx与s的大小相同，则-

    • 当k为0时返回，否则为0，否则返回1000

  • 如果memo [idx] [k]不等于-1，则-

    • 返回备忘录[idx] [k]

  • 如果k <= 0，则-

    • 返回信息

  • ans：= inf

  • 对于初始化i：= idx，当i <s的大小时，更新（将i增加1），执行-

    • ans：= ans和dp [idx] [i]的最小值+调用函数solve（s，i + 1，k-1，dp）

  • 返回memo [idx] [k] = ans

  • 在主要方法中，执行以下操作

  • n：= s的大小

  • 用-1填充备忘录

  • 定义一个大小为nxn的2D数组dp

  • 对于初始化l：= 2，当l <= n时，更新（将l增加1），-

    • 如果l与2相同，则-

    • dp [i] [j]：=当s [i]与s [j]不同时为true

    • 除此以外

    • dp [i] [j]：= dp [i + 1] [j-1] + 0，如果s [i]与s [j]相同

    • 对于初始化i：= 0，j：= l-1，当j <n时，更新（j增加1），（i增加1），-

    • 返回solve(s,0,k,dp)

    让我们看下面的实现以更好地理解-

    示例

    #include <bits/stdc++.h>
    using namespace std;
    typedef long long int lli;
    class Solution {
    public:
       int memo[105][105];
       lli solve(string s, int idx, int k, vector < vector <int> > &dp){
          if(idx == s.size()) {
             return k == 0? 0 : 1000;
          }
          if(memo[idx][k] != -1) return memo[idx][k];
          if(k <= 0)return INT_MAX;
          lli ans = INT_MAX;
          for(int i = idx; i < s.size(); i++){
             ans = min(ans, dp[idx][i] + solve(s, i + 1, k - 1, dp));
          }
          return memo[idx][k] = ans;
       }
       int palindromePartition(string s, int k) {
          int n = s.size();
          memset(memo, -1, sizeof(memo));
          vector < vector <int> > dp(n, vector <int>(n));
          for(int l =2; l <= n; l++){
             for(int i = 0, j = l - 1; j <n; j++, i++){
                if(l==2){
                   dp[i][j] = !(s[i] == s[j]);
                }else{
                   dp[i][j] = dp[i+1][j-1] + !(s[i] == s[j]);
                }
             }
          }
          return solve(s, 0, k, dp);
       }
    };
    main(){
       Solution ob;
       cout << (ob.palindromePartition("ababbc", 2));
    }

    输入项

    “ababbc”

    输出结果

    1

    以上是 C ++中的回文分割III 的全部内容， 来源链接： utcz.com/z/355843.html

    回到顶部