Dado un entero X y dos strings S1 y S2 , la tarea es verificar que la string S1 se pueda 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 cambio 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:
C++
// C++ implementation to check
// that a given string can be
// converted to another string
// by circular clockwise shift
// of each character by atmost
// X times
#include <bits/stdc++.h>
using namespace std;
// Function to check that all
// characters of s1 can be
// converted to s2 by circular
// clockwise shift atmost X times
void isConversionPossible(string s1,
string s2, int x)
{
int diff, 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[i] == s2[i])
continue;
// Calculate the difference
// between the ASCII values
// of the characters
diff = (int(s2[i] - s1[i])
+ 26)
% 26;
// If difference exceeds X
if (diff > x) {
cout << "NO" << endl;
return;
}
}
cout << "YES" << endl;
}
// Driver Code
int main()
{
string s1 = "you";
string s2 = "ara";
int x = 6;
// Function call
isConversionPossible(s1, s2, x);
return 0;
}
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
Python3
# Python3 implementation to check
# that the given string can be
# converted to another string
# by circular clockwise shift
# Function to check that the
# string s1 can be converted
# to s2 by clockwise circular
# shift of all characters of
# str1 atmost X times
def isConversionPossible(s1, s2, x):
n = len(s1)
s1 = list(s1)
s2 = list(s2)
for i in range(n):
# Difference between the
# ASCII numbers of characters
diff = ord(s2[i]) - ord(s1[i])
# If both characters
# are the same
if diff == 0:
continue
# Condition to check if the
# difference less than 0 then
# find the circular shift by
# adding 26 to it
if diff < 0:
diff = diff + 26
# If difference between
# their ASCII values
# exceeds X
if diff > x:
return False
return True
# Driver Code
if __name__ == "__main__":
s1 = "you"
s2 = "ara"
x = 6
# Function Call
result = isConversionPossible(s1, s2, x)
if result:
print("YES")
else:
print("NO")
C#
// C# implementation to check
// that a given string can be
// converted to another string
// by circular clockwise shift
// of each character by atmost
// X times
using System;
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[i] == s2[i])
continue;
// Calculate the difference
// between the ASCII values
// of the characters
diff = ((int)(s2[i] -
s1[i]) + 26) % 26;
// If difference exceeds X
if (diff > x)
{
Console.Write("NO");
return;
}
}
Console.Write("YES");
}
// Driver Code
public static void Main ()
{
String s1 = "you";
String s2 = "ara";
int x = 6;
// Function call
isConversionPossible(s1, s2, x);
}
}
// This code is contributed by chitranayal
Javascript
<script>
// Javascript implementation to check
// that a given string can be
// converted to another string
// by circular clockwise shift
// of each character by atmost
// X times
// Function to check that all
// characters of s1 can be
// converted to s2 by circular
// clockwise shift atmost X times
function isConversionPossible(s1,s2,x)
{
let 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(let i = 0; i < n; i++)
{
// If both the characters
// are same
if (s1[i] == s2[i])
continue;
// Calculate the difference
// between the ASCII values
// of the characters
diff = ((s2[i].charCodeAt(0) -
s1[i].charCodeAt(0)) + 26) % 26;
// If difference exceeds X
if (diff > x)
{
document.write("NO<br>");
return;
}
}
document.write("YES<br>");
}
// Driver Code
let s1 = "you";
let s2 = "ara";
let x = 6;
// Function call
isConversionPossible(s1, s2, x);
// This code is contributed by avanitrachhadiya2155
</script>
YES
Complejidad de tiempo: O(N),N=Longitud(S1)
Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por vishalarya1701 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA