Dadas dos strings S1 y S2 , la tarea es verificar si ambas strings se pueden igualar realizando la operación dada en la string S1 . En una sola operación, cualquier carácter en un índice impar se puede intercambiar con cualquier otro carácter en un índice impar, lo mismo ocurre con los caracteres en índices pares.
Ejemplos:
Entrada: S1 = “abcd”, S2 = “cbad”
Salida: Sí
Intercambie ‘a’ y ‘c’ en S1 y la
string resultante es igual a S2.
Entrada: S1 = “abcd”, S2 = “abcdcd”
Salida: No
Acercarse:
- Cree una string even_s1 a partir de los caracteres en los índices pares de S1 .
- Del mismo modo, genere las strings even_s2 , odd_s1 y odd_s2 .
- Ordene las cuatro strings de los pasos anteriores.
- Si par_s1 = par_s2 e impar_s1 = impar_s2 , imprima Sí .
- De lo contrario, imprima No , ya que las strings no se pueden hacer iguales.
A continuación se muestra la implementación del enfoque anterior:
C++
// CPP implementation of the approach
#include<bits/stdc++.h>
using namespace std;
// Function to return the string formed
// by the odd indexed characters of s
string partOdd(string s)
{
string st = "";
for(int i = 0; i < s.length(); i++)
{
if (i % 2 != 0)
st += s[i];
}
return st;
}
// Function to return the string formed
// by the even indexed characters of s
string partEven(string str)
{
string s = "";
for(int i = 0; i < str.length(); i++)
{
if (i % 2 == 0)
s += str[i];
}
return s;
}
// Function that returns true if s1
// can be made equal to s2
// with the given operation
bool canBeMadeEqual(string s1, string s2)
{
// Get the string formed by the
// even indexed characters of s1
string even_s1 = partEven(s1);
// Get the string formed by the
// even indexed characters of s2
string even_s2 = partEven(s2);
// Get the string formed by the
// odd indexed characters of s1
string odd_s1 = partOdd(s1);
// Get the string formed by the
// odd indexed characters of s2
string odd_s2 = partOdd(s2);
// Sorting all the lists
sort(even_s1.begin(), even_s1.end());
sort(even_s2.begin(), even_s2.end());
sort(odd_s1.begin(), odd_s1.end());
sort(odd_s2.begin(), odd_s2.end());
// If the strings can be made equal
if (even_s1 == even_s2 and odd_s1 == odd_s2)
return true;
return false;
}
// Driver code
int main()
{
string s1 = "cdab";
string s2 = "abcd";
if(canBeMadeEqual(s1, s2))
cout << "Yes" << endl;
else
cout << "No" << endl;
}
// This code is contributed by Surendra_Gangwar
Java
// Java implementation of the approach
import java.util.*;
class GFG
{
// Function to return the string formed
// by the odd indexed characters of s
static String partOdd(String s)
{
String st = "";
for (int i = 0; i < s.length(); i++)
{
if (i % 2 != 0)
st += s.charAt(i);
}
return st;
}
// Function to return the string formed
// by the even indexed characters of s
static String partEven(String str)
{
String s = "";
for (int i = 0; i < str.length(); i++)
{
if (i % 2 == 0)
s += str.charAt(i);
}
return s;
}
// Function that returns true if s1
// can be made equal to s2
// with the given operation
static boolean canBeMadeEqual(String s1,
String s2)
{
// Get the string formed by the
// even indexed characters of s1
char[] even1 = partEven(s1).toCharArray();
// Get the string formed by the
// even indexed characters of s2
char[] even2 = partEven(s2).toCharArray();
// Get the string formed by the
// odd indexed characters of s1
char[] odd1 = partOdd(s1).toCharArray();
// Get the string formed by the
// odd indexed characters of s2
char[] odd2 = partOdd(s2).toCharArray();
// Sorting all the lists
Arrays.sort(even1);
Arrays.sort(even2);
Arrays.sort(odd1);
Arrays.sort(odd2);
String even_s1 = new String(even1);
String even_s2 = new String(even2);
String odd_s1 = new String(odd1);
String odd_s2 = new String(odd2);
// If the strings can be made equal
if (even_s1.equals(even_s2) &&
odd_s1.equals(odd_s2))
return true;
return false;
}
// Driver Code
public static void main(String[] args)
{
String s1 = "cdab";
String s2 = "abcd";
if (canBeMadeEqual(s1, s2))
System.out.println("Yes");
else
System.out.println("No");
}
}
// This code is contributed by
// sanjeev2552
Python3
# Python3 implementation of the approach
# Function to return the string formed
# by the odd indexed characters of s
def partOdd(s):
odd = []
for i in range(len(s)):
if i % 2 != 0:
odd.append(s[i])
return odd
# Function to return the string formed
# by the even indexed characters of s
def partEven(s):
even = []
for i in range(len(s)):
if i % 2 == 0:
even.append(s[i])
return even
# Function that returns true if s1
# can be made equal to s2
# with the given operation
def canBeMadeEqual(s1, s2):
# Get the string formed by the
# even indexed characters of s1
even_s1 = partEven(s1)
# Get the string formed by the
# even indexed characters of s2
even_s2 = partEven(s2)
# Get the string formed by the
# odd indexed characters of s1
odd_s1 = partOdd(s1)
# Get the string formed by the
# odd indexed characters of s2
odd_s2 = partOdd(s2)
# Sorting all the lists
even_s1.sort()
even_s2.sort()
odd_s1.sort()
odd_s2.sort()
# If the strings can be made equal
if even_s1 == even_s2 and odd_s1 == odd_s2:
return True
return False
# Driver code
s1 = "cdab"
s2 = "abcd"
if canBeMadeEqual(s1, s2):
print("Yes")
else:
print("No")
C#
// C# implementation of the approach
using System;
class GFG
{
// Function to return the string formed
// by the odd indexed characters of s
static string partOdd(string s)
{
string st = "";
for (int i = 0; i < s.Length; i++)
{
if (i % 2 != 0)
st += s[i];
}
return st;
}
// Function to return the string formed
// by the even indexed characters of s
static string partEven(string str)
{
string s = "";
for (int i = 0; i < str.Length; i++)
{
if (i % 2 == 0)
s += str[i];
}
return s;
}
// Function that returns true if s1
// can be made equal to s2
// with the given operation
static bool canBeMadeEqual(string s1,
string s2)
{
// Get the string formed by the
// even indexed characters of s1
char[] even1 = partEven(s1).ToCharArray();
// Get the string formed by the
// even indexed characters of s2
char[] even2 = partEven(s2).ToCharArray();
// Get the string formed by the
// odd indexed characters of s1
char[] odd1 = partOdd(s1).ToCharArray();
// Get the string formed by the
// odd indexed characters of s2
char[] odd2 = partOdd(s2).ToCharArray();
// Sorting all the lists
Array.Sort(even1);
Array.Sort(even2);
Array.Sort(odd1);
Array.Sort(odd2);
string even_s1 = new string(even1);
string even_s2 = new string(even2);
string odd_s1 = new string(odd1);
string odd_s2 = new string(odd2);
// If the strings can be made equal
if (even_s1.Equals(even_s2) &&
odd_s1.Equals(odd_s2))
return true;
return false;
}
// Driver Code
public static void Main()
{
string s1 = "cdab";
string s2 = "abcd";
if (canBeMadeEqual(s1, s2))
Console.Write("Yes");
else
Console.Write("No");
}
}
// This code is contributed by AbhiThakur
Javascript
<script>
// JavaScript implementation of the approach
// Function to return the string formed
// by the odd indexed characters of s
function partOdd(s) {
var st = "";
for (var i = 0; i < s.length; i++) {
if (i % 2 !== 0) st += s[i];
}
return st;
}
// Function to return the string formed
// by the even indexed characters of s
function partEven(str) {
var s = "";
for (var i = 0; i < str.length; i++) {
if (i % 2 === 0) s += str[i];
}
return s;
}
// Function that returns true if s1
// can be made equal to s2
// with the given operation
function canBeMadeEqual(s1, s2) {
// Get the string formed by the
// even indexed characters of s1
var even1 = partEven(s1).split("");
// Get the string formed by the
// even indexed characters of s2
var even2 = partEven(s2).split("");
// Get the string formed by the
// odd indexed characters of s1
var odd1 = partOdd(s1).split("");
// Get the string formed by the
// odd indexed characters of s2
var odd2 = partOdd(s2).split("");
// Sorting all the lists
even1.sort();
even2.sort();
odd1.sort();
odd2.sort();
var even_s1 = even1.join("");
var even_s2 = even2.join("");
var odd_s1 = odd1.join("");
var odd_s2 = odd2.join("");
// If the strings can be made equal
if (even_s1 === even_s2 && odd_s1 === odd_s2) return true;
return false;
}
// Driver Code
var s1 = "cdab";
var s2 = "abcd";
if (canBeMadeEqual(s1, s2)) document.write("Yes");
else document.write("No");
</script>
Producción:
Yes
Complejidad de tiempo: O(n*log(n)+m*log(m)) donde n y m son las longitudes de la string.
Espacio Auxiliar: O(n+m)
Publicación traducida automáticamente
Artículo escrito por imran_shaik y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA