Dadas dos strings X e Y de longitud N , la tarea es verificar si ambas strings pueden igualarse invirtiendo cualquier substring de X exactamente una vez. Si es posible, escriba «Sí» . De lo contrario, escriba “No” .
Ejemplos:
Entrada: X = “adcbef”, Y = “abcdef”
Salida: Sí
Explicación: Las strings se pueden igualar invirtiendo la substring “dcb” de la string X.Entrada: X = “126543”, Y = “123456”
Salida: Sí
Explicación: Las strings se pueden igualar invirtiendo la substring “6543” de la string X.
Enfoque ingenuo: el enfoque más simple para resolver el problema es invertir todas las substrings posibles de la string X y, para cada inversión, verificar si ambas strings son iguales. Si se determina que es cierto después de cualquier reversión, imprima «Sí» . De lo contrario, escriba “No”.
Complejidad de Tiempo: O(N 2 )
Espacio Auxiliar: O(1)
Enfoque eficiente: para optimizar el enfoque anterior, siga los pasos a continuación para resolver el problema:
- Inicialice una variable, digamos L como -1 , para almacenar el primer índice desde la izquierda que tenga caracteres desiguales en las dos strings.
- Recorra la string X sobre el rango [0, N – 1] usando una variable i y si para cualquier índice, si se encuentra que los caracteres en las dos strings no son iguales, establezca L = i y salga del ciclo .
- Inicialice una variable, digamos R como -1 , para almacenar el primer índice desde la derecha que tenga caracteres desiguales en las dos strings.
- Recorra la string X sobre el rango [N – 1, 0] usando la variable i y si para cualquier índice, si los caracteres en las dos strings son desiguales, establezca R = i y salga del ciclo .
- Invierta los caracteres de la string X sobre los índices [L, R] .
- Después de completar los pasos anteriores, verifique si ambas strings son iguales o no. Si se encuentra igual, imprima «Sí» . De lo contrario, escriba “No” .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to check if the strings
// can be made equal or not by
// reversing a substring of X
bool checkString(string X, string Y)
{
// Store the first index from
// the left which contains unequal
// characters in both the strings
int L = -1;
// Store the first element from
// the right which contains unequal
// characters in both the strings
int R = -1;
// Checks for the first index from
// left in which characters in both
// the strings are unequal
for (int i = 0; i < X.length(); ++i) {
if (X[i] != Y[i]) {
// Store the current index
L = i;
// Break out of the loop
break;
}
}
// Checks for the first index from
// right in which characters in both
// the strings are unequal
for (int i = X.length() - 1; i > 0; --i) {
if (X[i] != Y[i]) {
// Store the current index
R = i;
// Break out of the loop
break;
}
}
// Reverse the substring X[L, R]
reverse(X.begin() + L,
X.begin() + R + 1);
// If X and Y are equal
if (X == Y) {
cout << "Yes";
}
// Otherwise
else {
cout << "No";
}
}
// Driver Code
int main()
{
string X = "adcbef", Y = "abcdef";
// Function Call
checkString(X, Y);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG{
// Function to check if the Strings
// can be made equal or not by
// reversing a subString of X
static void checkString(String X, String Y)
{
// Store the first index from
// the left which contains unequal
// characters in both the Strings
int L = -1;
// Store the first element from
// the right which contains unequal
// characters in both the Strings
int R = -1;
// Checks for the first index from
// left in which characters in both
// the Strings are unequal
for (int i = 0; i < X.length(); ++i) {
if (X.charAt(i) != Y.charAt(i)) {
// Store the current index
L = i;
// Break out of the loop
break;
}
}
// Checks for the first index from
// right in which characters in both
// the Strings are unequal
for (int i = X.length() - 1; i > 0; --i) {
if (X.charAt(i) != Y.charAt(i)) {
// Store the current index
R = i;
// Break out of the loop
break;
}
}
// Reverse the subString X[L, R]
X = X.substring(0, L) +
reverse(X.substring(L, R + 1)) +
X.substring(R + 1);
// If X and Y are equal
if (X.equals(Y)) {
System.out.print("Yes");
}
// Otherwise
else {
System.out.print("No");
}
}
static String reverse(String input) {
char[] a = input.toCharArray();
int l, r = a.length - 1;
for (l = 0; l < r; l++, r--) {
char temp = a[l];
a[l] = a[r];
a[r] = temp;
}
return String.valueOf(a);
}
// Driver Code
public static void main(String[] args)
{
String X = "adcbef", Y = "abcdef";
// Function Call
checkString(X, Y);
}
}
// This code is contributed by 29AjayKumar
Python3
# Python3 program for the above approach
# Function to check if the strings
# can be made equal or not by
# reversing a substring of X
def checkString(X, Y):
# Store the first index from
# the left which contains unequal
# characters in both the strings
L = -1
# Store the first element from
# the right which contains unequal
# characters in both the strings
R = -1
# Checks for the first index from
# left in which characters in both
# the strings are unequal
for i in range(len(X)):
if (X[i] != Y[i]):
# Store the current index
L = i
# Break out of the loop
break
# Checks for the first index from
# right in which characters in both
# the strings are unequal
for i in range(len(X) - 1, 0, -1):
if (X[i] != Y[i]):
# Store the current index
R = i
# Break out of the loop
break
X = list(X)
X = X[:L] + X[R : L - 1 : -1 ] + X[R + 1:]
# If X and Y are equal
if (X == list(Y)):
print("Yes")
# Otherwise
else:
print("No")
# Driver Code
if __name__ == "__main__" :
X = "adcbef"
Y = "abcdef"
# Function Call
checkString(X, Y)
# This code is contributed by AnkThon
C#
// C# program for the above approach
using System;
class GFG{
// Function to check if the Strings
// can be made equal or not by
// reversing a subString of X
static void checkString(String X, String Y)
{
// Store the first index from
// the left which contains unequal
// characters in both the Strings
int L = -1;
// Store the first element from
// the right which contains unequal
// characters in both the Strings
int R = -1;
// Checks for the first index from
// left in which characters in both
// the Strings are unequal
for(int i = 0; i < X.Length; ++i)
{
if (X[i] != Y[i])
{
// Store the current index
L = i;
// Break out of the loop
break;
}
}
// Checks for the first index from
// right in which characters in both
// the Strings are unequal
for(int i = X.Length - 1; i > 0; --i)
{
if (X[i] != Y[i])
{
// Store the current index
R = i;
// Break out of the loop
break;
}
}
// Reverse the subString X[L, R]
X = X.Substring(0, L) +
reverse(X.Substring(L, R + 1 - L)) +
X.Substring(R + 1);
// If X and Y are equal
if (X.Equals(Y))
{
Console.Write("Yes");
}
// Otherwise
else
{
Console.Write("No");
}
}
static String reverse(String input)
{
char[] a = input.ToCharArray();
int l, r = a.Length - 1;
for(l = 0; l < r; l++, r--)
{
char temp = a[l];
a[l] = a[r];
a[r] = temp;
}
return String.Join("",a);
}
// Driver Code
public static void Main(String[] args)
{
String X = "adcbef", Y = "abcdef";
// Function Call
checkString(X, Y);
}
}
// This code is contributed by Amit Katiyar
Javascript
<script>
// JavaScript program for the above approach
// Function to check if the Strings
// can be made equal or not by
// reversing a subString of X
function checkString(X, Y) {
// Store the first index from
// the left which contains unequal
// characters in both the Strings
var L = -1;
// Store the first element from
// the right which contains unequal
// characters in both the Strings
var R = -1;
// Checks for the first index from
// left in which characters in both
// the Strings are unequal
for (var i = 0; i < X.length; ++i) {
if (X[i] !== Y[i]) {
// Store the current index
L = i;
// Break out of the loop
break;
}
}
// Checks for the first index from
// right in which characters in both
// the Strings are unequal
for (var i = X.length - 1; i > 0; --i) {
if (X[i] !== Y[i]) {
// Store the current index
R = i;
// Break out of the loop
break;
}
}
// Reverse the subString X[L, R]
X =
X.substring(0, L) +
reverse(X.substring(L, R + 1)) +
X.substring(R + 1);
// If X and Y are equal
if (X === Y) {
document.write("Yes");
}
// Otherwise
else {
document.write("No");
}
}
function reverse(input) {
var a = input.split("");
var l,
r = a.length - 1;
for (l = 0; l < r; l++, r--) {
var temp = a[l];
a[l] = a[r];
a[r] = temp;
}
return a.join("");
}
// Driver Code
var X = "adcbef",
Y = "abcdef";
// Function Call
checkString(X, Y);
</script>
Producción:
Yes
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por pushpendrayadav1057 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA