Dado un entero X y dos strings S1 y S2 , la tarea es comprobar que la string S1 se puede convertir en la string S2 cambiando los caracteres circularmente en el sentido de las agujas del reloj como máximo X veces.
Entrada: S1 = “abcd”, S2 = “dddd”, X = 3
Salida: Sí
Explicación:
La string dada S1 se puede convertir en la string S2 como
: Carácter “a” – Cambiar 3 veces – “d”
Carácter “b” – Desplazar 2 veces – “d”
Carácter “c” – Desplazar 1 vez – “d”
Carácter “d” – Desplazar 0 veces – “d”Entrada: S1 = “usted”, S2 = “ara”, X = 6
Salida: Sí
Explicación:
La string dada S1 se puede convertir en la string S2 como –
Carácter “y” – Desplazamiento circular 2 veces – “a”
Carácter “o” – Desplazamiento 3 veces – “r”
Carácter “u” – Desplazamiento circular 6 veces – “a”
Enfoque: La idea es recorrer la string y para cada índice y encontrar la diferencia entre los valores ASCII del carácter en los índices respectivos de las dos strings. Si la diferencia es menor que 0, entonces para un desplazamiento circular, suma 26 para obtener la diferencia real. Si para cualquier índice, la diferencia excede X , entonces S2 no se puede formar a partir de S1 , de lo contrario es posible.
A continuación se muestra la implementación del enfoque anterior:
Java
// Java implementation to check
// that a given string can be
// converted to another string
// by circular clockwise shift
// of each character by atmost
// X times
import java.io.*;
import java.util.*;
class GFG{
// Function to check that all
// characters of s1 can be
// converted to s2 by circular
// clockwise shift atmost X times
static void isConversionPossible(String s1,
String s2,
int x)
{
int diff = 0, n;
n = s1.length();
// Check for all characters of
// the strings whether the
// difference between their
// ascii values is less than
// X or not
for(int i = 0; i < n; i++)
{
// If both the characters
// are same
if (s1.charAt(i) == s2.charAt(i))
continue;
// Calculate the difference
// between the ASCII values
// of the characters
diff = ((int)(s2.charAt(i) -
s1.charAt(i)) + 26) % 26;
// If difference exceeds X
if (diff > x)
{
System.out.println("NO");
return;
}
}
System.out.println("YES");
}
// Driver Code
public static void main (String[] args)
{
String s1 = "you";
String s2 = "ara";
int x = 6;
// Function call
isConversionPossible(s1, s2, x);
}
}
// This code is contributed by Ganeshchowdharysadanala
YES
Complejidad de tiempo: O(N),N=Longitud(S1)
Espacio Auxiliar: O(1)
¡ Consulte el artículo completo sobre Comprobar si se puede formar una string a partir de otra string con un máximo de X cambios circulares en el sentido de las agujas del reloj para obtener más detalles!
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