使用最少的给定操作数将一个字符串转换为另一个字符串

本文概述

``````Input:  A = "ABD", B = "BAD"
Output: 1
Explanation: Pick B and insert it at front.

Input:  A = "EACBD", B = "EABCD"
Output: 3
Explanation: Pick B and insert at front, EACBD => BEACD
Pick A and insert at front, BEACD => ABECD
Pick E and insert at front, ABECD => EABCD``````

1)通过首先为A的所有字符创建一个计数数组, 然后与B一起检查B是否对每个字符都有相同的计数, 来查找A是否可以转换为B。

2)将结果初始化为0。

2)从两个字符串的末尾开始遍历。

……a)如果A和B的当前字符匹配, 即A [i] == B [j]

………那么我= i-1和j = j-1

……b)如果当前字符不匹配, 则在剩余字符中搜索B [j]

………一种。搜索时, 请保持递增结果, 因为这些字符

…………必须向前推进以实现A到B的转型。

C ++

``````// C++ program to find minimum number of
// operations required to transform one string to other
#include<bits/stdc++.h>
using namespace std;

// Function to find minimum number of operations required to transform
// A to B.
int minOps(string& A, string& B)
{
int m = A.length(), n = B.length();

// This parts checks whether conversion is
// possible or not
if (n != m)
return -1;
int count[256];
memset (count, 0, sizeof (count));
for ( int i=0; i<n; i++)   // count characters in A
count[B[i]]++;
for ( int i=0; i<n; i++)   // subtract count for
count[A[i]]--;         // every character in B
for ( int i=0; i<256; i++)   // Check if all counts become 0
if (count[i])
return -1;

// This part calculates the number of operations required
int res = 0;
for ( int i=n-1, j=n-1; i>=0; )
{
// If there is a mismatch, then keep incrementing
while (i>=0 && A[i] != B[j])
{
i--;
res++;
}

// If A[i] and B[j] match
if (i >= 0)
{
i--;
j--;
}
}
return res;
}

// Driver program
int main()
{
string A = "EACBD" ;
string B = "EABCD" ;
cout << "Minimum number of operations "
"required is " << minOps(A, B);
return 0;
}``````

Java

``````// Java program to find minimum number of
// operations required to transform one
// string to other
import java.io.*;
import java.util.*;

public class GFG {

// Function to find minimum number of
// operations required to transform
// A to B.
public static int minOps(String A, String B)
{

// This parts checks whether conversion is
// possible or not
if (A.length() != B.length())
return - 1 ;

int i, j, res = 0 ;
int count [] = new int [ 256 ];

// count characters in A

// subtract count for every character in B
for (i = 0 ; i < A.length(); i++)
{
count[A.charAt(i)]++;
count[B.charAt(i)]--;
}

// Check if all counts become 0
for (i = 0 ; i < 256 ; i++)
if (count[i] != 0 )
return - 1 ;

i = A.length() - 1 ;
j = B.length() - 1 ;

while (i >= 0 )
{
// If there is a mismatch, then
// keep incrementing result 'res'
if (A.charAt(i) != B.charAt(j))
res++;
else
j--;
i--;
}
return res;
}

// Driver code
public static void main(String[] args)
{
String A = "EACBD" ;
String B = "EABCD" ;

System.out.println( "Minimum number of "
+ "operations required is "
+ minOps(A, B));
}
}

// This code is contributed by Dipesh Jain
// (dipesh_jain)``````

python

``````# Python program to find the minimum number of
# operations required to transform one string to other

# Function to find minimum number of operations required
# to transform A to B
def minOps(A, B):
m = len (A)
n = len (B)

# This part checks whether conversion is possible or not
if n ! = m:
return - 1

count = [ 0 ] * 256

for i in xrange (n):        # count characters in A
count[ ord (B[i])] + = 1
for i in xrange (n):        # subtract count for every char in B
count[ ord (A[i])] - = 1
for i in xrange ( 256 ):    # Check if all counts become 0
if count[i]:
return - 1

# This part calculates the number of operations required
res = 0
i = n - 1
j = n - 1
while i > = 0 :

# if there is a mismatch, then keep incrementing
while i> = 0 and A[i] ! = B[j]:
i - = 1
res + = 1

# if A[i] and B[j] match
if i > = 0 :
i - = 1
j - = 1

return res

# Driver program
A = "EACBD"
B = "EABCD"
print "Minimum number of operations required is " + str (minOps(A, B))
# This code is contributed by Bhavya Jain``````

C#

``````// C# program to find minimum number of
// operations required to transform one
// string to other
using System;

class GFG
{

// Function to find minimum number of
// operations required to transform
// A to B.
public static int minOps( string A, string B)
{

// This parts checks whether
// conversion is possible or not
if (A.Length != B.Length)
{
return -1;
}

int i, j, res = 0;
int [] count = new int [256];

// count characters in A

// subtract count for every
// character in B
for (i = 0; i < A.Length; i++)
{
count[A[i]]++;
count[B[i]]--;
}

// Check if all counts become 0
for (i = 0; i < 256; i++)
{
if (count[i] != 0)
{
return -1;
}
}

i = A.Length - 1;
j = B.Length - 1;

while (i >= 0)
{
// If there is a mismatch, then
// keep incrementing result 'res'
if (A[i] != B[j])
{
res++;
}
else
{
j--;
}
i--;
}
return res;
}

// Driver code
public static void Main( string [] args)
{
string A = "EACBD" ;
string B = "EABCD" ;

Console.WriteLine( "Minimum number of " +
"operations required is " +
minOps(A, B));
}
}

// This code is contributed by Shrikant13``````

的PHP

``````<?php
// PHP program to find minimum number of
// operations required to transform one string to other

// Function to find minimum number of operations required to transform
// A to B.
function minOps( \$A , \$B )
{
\$m = strlen ( \$A );
\$n = strlen ( \$B );

// This parts checks whether conversion is
// possible or not
if ( \$n != \$m )
return -1;
\$count = array_fill (0, 256, NULL);
for ( \$i =0; \$i < \$n ; \$i ++)   // count characters in A
\$count [ord( \$B [ \$i ])]++;
for ( \$i =0; \$i < \$n ; \$i ++)   // subtract count for
\$count [ord( \$A [ \$i ])]--;         // every character in B
for ( \$i =0; \$i <256; \$i ++)   // Check if all counts become 0
if ( \$count [ \$i ])
return -1;

// This part calculates the number of operations required
\$res = 0;
for ( \$i = \$n -1, \$j = \$n -1; \$i >=0; )
{
// If there is a mismatch, then keep incrementing
while ( \$i >=0 && \$A [ \$i ] != \$B [ \$j ])
{
\$i --;
\$res ++;
}

// If A[i] and B[j] match
if ( \$i >= 0)
{
\$i --;
\$j --;
}
}
return \$res ;
}

// Driver program

\$A = "EACBD" ;
\$B = "EABCD" ;
echo "Minimum number of operations " .
"required is " . minOps( \$A , \$B );
return 0;
?>``````

``Minimum number of operations required is 3``