时间戳

首页 > 解决方案 > 使用给定子字符串将给定字符串转换为回文

c++ - 使用给定子字符串将给定字符串转换为回文

问题描述

给定一个字符串 S1 和字符串 S2。将字符串 S1 转换为回文字符串，例如 S2 是该回文字符串的子字符串。在 S1 上允许的唯一操作是用任何其他字符替换任何字符。找到所需的最小操作数。

我已经编写了这段代码，可以计算需要对常规字符串进行多少次更改才能生成回文，但我不知道如何使它工作让我们说输入 asstring n = "aaaaa" and string (substring) m = "bbb"并且输出必须是3，因为abbba在这种情况下，需要进行三处更改才能制作字符串

这是我的代码

#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
int main()
{
    string n = "aaaaa";
    string m = "bbb";

    if (n.size() <= m.size())
    {
        cnt = -1
    }

    if (n.size() > m.size())
    {
        string x, y;

       int cnt=0;

       if(n.size()%2!=0)
          {
                x=n.substr(0,n.size()/2);
                y=n.substr(n.size()/2+1);
               reverse(y.begin(),y.end());
          }
            else if(n.size()%2==0)
            {
                x=n.substr(0,n.size()/2);
                y=n.substr(n.size()/2);
                reverse(y.begin(),y.end());
            }
                for(int i=0;i<n.size();i++)
                    if(x[i]!=y[i])
                    cnt++;
              cout<<cnt<<endl;
    }

  }

标签： c++string

解决方案

逻辑是将 s2 放在 s1 中的每个位置并计算相同的成本。输出其中的最小成本。该算法的时间复杂度为 O(n^2)。

#include<bits/stdc++.h>
using namespace std;

int main(){

    string s1,s2;
    cin>>s1>>s2;
    int l1=s1.length(),l2=s2.length();
    int ans=INT_MAX;
    if(l2>l1){

        cout<<-1<<endl; // not possible
        return 0;
    }
    for(int i=0 ; i<l1-l2+1 ; i++){

        string temp=s1.substr(0,i)+s2+s1.substr(i+l2); // place s2 in all possible positions in s1
        int cost=0;
        // calculate cost to place s2
        for(int j=i ; j<i+l2 ; j++){

            if(s1[j]!=temp[j])
                cost++;
        }
        int z=0;
        // find the cost to convert new string to palindrome
        for(int j=0 ; j<ceil(l1/2.0) ; j++){

            if((j<i || j>=i+l2) && temp[j]!=temp[l1-j-1]) // if s2 is in the first half of new string
                cost++;
            else if(temp[j]!=temp[l1-j-1] && (l1-j-1<i || l1-j-1>=i+l2)) // if s2 is in the second half of new string
                cost++;
            else if(temp[j]!=temp[l1-j-1]){ // if s2 is in both halves

                z=1;
                break;
            }
        }
        if(z==0)
            ans=min(ans,cost);
    }
    if(ans==INT_MAX)
        cout<<-1<<endl;
    else
        cout<<ans<<endl;
    return 0;
}

推荐阅读