Dadas dos strings A y B, la tarea es convertir A en B si es posible. La única operación permitida es poner cualquier carácter de A e insertarlo al frente. Encuentra si es posible convertir la string. Si es así, entonces salida mínima no. de operaciones requeridas para la transformación.
Ejemplos:
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
Verificar si una string se puede transformar en otra es simple. Necesitamos verificar si ambas strings tienen la misma cantidad de caracteres y el mismo conjunto de caracteres. Esto se puede hacer fácilmente creando una array de conteo para la primera string y verificando si la segunda string tiene el mismo conteo de cada carácter.
¿Cómo encontrar el número mínimo de operaciones cuando estamos seguros de que podemos transformar A en B? La idea es comenzar a hacer coincidir desde los últimos caracteres de ambas strings. Si los últimos caracteres coinciden, nuestra tarea se reduce a n-1 caracteres. Si los últimos caracteres no coinciden, encuentre la posición del carácter que no coincide de B en A. La diferencia entre dos posiciones indica que estos muchos caracteres de A deben moverse antes del carácter actual de A.
A continuación se muestra el algoritmo completo.
1) Averigüe si A se puede transformar en B o no creando primero una array de conteo para todos los caracteres de A, luego verifique con B si B tiene el mismo conteo para cada carácter.
2) Inicialice el resultado como 0.
3) Comience a atravesar desde el final de ambas strings.
……a) Si los caracteres actuales de A y B coinciden, es decir, A[i] == B[j]
………entonces i = i-1 y j = j-1
b) Si los caracteres actuales no coinciden , luego busque B[j] en
………A restante. Mientras busca, siga incrementando el resultado ya que estos caracteres
………deben avanzar para la transformación de A a B.
A continuación se muestran las implementaciones basadas en esta idea.
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));
// count characters in A
for (int i = 0; i < n; i++)
count[A[i]]++;
// subtract count for every character in B
for (int i = 0; i < n; i++)
count[B[i]]--;
// Check if all counts become 0
for (int i = 0; i < 256; i++)
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
// result 'res' until B[j] is not found in A[0..i]
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;
}
// This code is contributed by Aditya Kumar (adityakumar129)
C
// C program to find minimum number of operations required
// to transform one string to other
#include <stdio.h>
#include <string.h>
// Function to find minimum number of operations required to
// transform A to B.
int minOps(char A[], char B[])
{
int m = strlen(A), n = strlen(B);
// This parts checks whether conversion is
// possible or not
if (n != m)
return -1;
int count[256];
for (int i = 0; i < 256; i++)
count[i] = 0;
// count characters in A
for (int i = 0; i < n; i++)
count[A[i]]++;
// subtract count for every character in B
for (int i = 0; i < n; i++)
count[B[i]]--;
// Check if all counts become 0
for (int i = 0; i < 256; i++)
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
// result 'res' until B[j] is not found in A[0..i]
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()
{
char A[] = "EACBD";
char B[] = "EABCD";
printf("Minimum number of operations required is %d", minOps(A, B));
return 0;
}
// This code is contributed by Aditya Kumar (adityakumar129)
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' until B[j] is not
// found in A[0..i]
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 Aditya Kumar (adityakumar129)
Python3
# 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 range(n): # count characters in A
count[ord(B[i])] += 1
for i in range(n): # subtract count for every char in B
count[ord(A[i])] -= 1
for i in range(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
# result 'res' until B[j] is not found in A[0..i]
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'
// until B[j] is not found in A[0..i]
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
// result 'res' until B[j] is not found in A[0..i]
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;
?>
Javascript
<script>
// Javascript 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)
{
// This parts checks whether conversion
// is possible or not
if (A.length != B.length)
return -1;
let i, j, res = 0;
let count = new Array(256);
for(let i = 0; i < 256; i++)
{
count[i] = 0;
}
// count characters in A
// Subtract count for every character in B
for(i = 0; i < A.length; i++)
{
count[A[i].charCodeAt(0)]++;
count[B[i].charCodeAt(0)]--;
}
// 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'
// until B[j] is not found in A[0..i]
if (A[i] != B[j])
res++;
else
j--;
i--;
}
return res;
}
// Driver code
let A = "EACBD";
let B = "EABCD";
document.write("Minimum number of " +
"operations required is " +
minOps(A, B));
// This code is contributed by avanitrachhadiya2155
</script>
Producción:
Minimum number of operations required is 3
Complejidad de tiempo: O(n), tenga en cuenta que i siempre se decrementa (en el ciclo while y en if), y el ciclo for comienza desde n-1 y se ejecuta mientras i >= 0.
Espacio Auxiliar: O(1).
Gracias a Gaurav Ahirwar por la solución anterior.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA