Dadas dos strings str1 y str2 , la tarea es verificar si una string str1 se puede convertir en una string str2 realizando las siguientes operaciones cualquier número de veces:
- Intercambia dos caracteres cualesquiera de str1 .
- Intercambia todas las apariciones de un carácter de str1 por todas las apariciones de cualquier otro carácter distinto de str1 .
Ejemplos:
Entrada: str1 = “xyyzzlll”, str2 = “yllzzxxx”
Salida: Verdadero
Explicación:
Intercambiar todas las apariciones de str1[0] y str1[1] modifica str1 a “yxxzzlll”
Intercambiar todas las apariciones de str1[1] y str1[5] modifica str1 a «yllzzxxx»
Dado que str1 y str2 son iguales, por lo tanto, la salida requerida es True.Entrada: str1 = “xyyzzavl”, str2 = “yllzzvac”
Salida: Falso
Enfoque: El problema se puede resolver usando la técnica Greedy . Siga los pasos a continuación para resolver el problema:
- Inicialice dos arrays , digamos hash1[256] y hash2[256] para almacenar la frecuencia de cada elemento distinto de str1 y str2 respectivamente.
- Inicialice dos conjuntos , digamos st1 y st2 para almacenar los distintos caracteres de str1 y str2 .
- Recorra la string y almacene la frecuencia de cada carácter distinto de str1 y str2 .
- Ordenar array hash1[] y hash2[] .
- Si st1 y st2 no son iguales, imprima falso.
- Recorra la array hash1 [] y hash2[] usando la variable i y verifique si el valor de (hash1[i] != hash2[i]) es verdadero o no. Si se encuentra que es verdadero, imprima Falso .
- De lo contrario, imprime True .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
bool checkStr1CanConStr2(string& str1,
string& str2)
{
// Stores length of str1
int N = str1.length();
// Stores length of str2
int M = str2.length();
// Stores distinct characters
// of str1
set<int> st1;
// Stores distinct characters
// of str2
set<int> st2;
// Stores frequency of
// each character of str1
int hash1[256] = { 0 };
// Traverse the string str1
for (int i = 0; i < N; i++) {
// Update frequency
// of str1[i]
hash1[str1[i]]++;
}
// Traverse the string str1
for (int i = 0; i < N; i++) {
// Insert str1[i]
// into st1
st1.insert(str1[i]);
}
// Traverse the string str2
for (int i = 0; i < M; i++) {
// Insert str1[i]
// into st1
st2.insert(str2[i]);
}
// If distinct characters in
// str1 and str2 are not same
if (st1 != st2) {
return false;
}
// Stores frequency of
// each character of str2
int hash2[256] = { 0 };
// Traverse the string str2
for (int i = 0; i < M; i++) {
// Update frequency
// of str2[i]
hash2[str2[i]]++;
}
// Sort hash1[] array
sort(hash1, hash1 + 256);
// Sort hash2[] array
sort(hash2, hash2 + 256);
// Traverse hash1[] and hash2[]
for (int i = 0; i < 256; i++) {
// If hash1[i] not
// equal to hash2[i]
if (hash1[i] != hash2[i]) {
return false;
}
}
return true;
}
// Driver Code
int main()
{
string str1 = "xyyzzlll";
string str2 = "yllzzxxx";
if (checkStr1CanConStr2(str1, str2)) {
cout << "True";
}
else {
cout << "False";
}
}
Java
// Java program to implement
// the above approach
import java.util.*;
class GFG{
static boolean checkStr1CanConStr2(String str1,
String str2)
{
// Stores length of str1
int N = str1.length();
// Stores length of str2
int M = str2.length();
// Stores distinct characters
// of str1
HashSet<Integer> st1 = new HashSet<>();
// Stores distinct characters
// of str2
HashSet<Integer> st2 = new HashSet<>();
// Stores frequency of
// each character of str1
int hash1[] = new int[256];
// Traverse the String str1
for (int i = 0; i < N; i++)
{
// Update frequency
// of str1[i]
hash1[str1.charAt(i)]++;
}
// Traverse the String str1
for (int i = 0; i < N; i++)
{
// Insert str1[i]
// into st1
st1.add((int)str1.charAt(i));
}
// Traverse the String str2
for (int i = 0; i < M; i++)
{
// Insert str1[i]
// into st1
st2.add((int)str2.charAt(i));
}
// If distinct characters in
// str1 and str2 are not same
if (!st1.equals(st2))
{
return false;
}
// Stores frequency of
// each character of str2
int hash2[] = new int[256];
// Traverse the String str2
for (int i = 0; i < M; i++)
{
// Update frequency
// of str2[i]
hash2[str2.charAt(i)]++;
}
// Sort hash1[] array
Arrays.sort(hash1);
// Sort hash2[] array
Arrays.sort(hash2);
// Traverse hash1[] and hash2[]
for (int i = 0; i < 256; i++)
{
// If hash1[i] not
// equal to hash2[i]
if (hash1[i] != hash2[i])
{
return false;
}
}
return true;
}
// Driver Code
public static void main(String[] args)
{
String str1 = "xyyzzlll";
String str2 = "yllzzxxx";
if (checkStr1CanConStr2(str1, str2))
{
System.out.print("True");
}
else
{
System.out.print("False");
}
}
}
// This code is contributed by 29AjayKumar
Python3
# Python3 program to implement
# the above approach
def checkStr1CanConStr2(str1, str2):
# Stores length of str1
N = len(str1)
# Stores length of str2
M = len(str2)
# Stores distinct characters
# of str1
st1 = set([])
# Stores distinct characters
# of str2
st2 = set([])
# Stores frequency of
# each character of str1
hash1 = [0] * 256
# Traverse the string str1
for i in range(N):
# Update frequency
# of str1[i]
hash1[ord(str1[i])] += 1
# Traverse the string str1
for i in range(N):
# Insert str1[i]
# into st1
st1.add(str1[i])
# Traverse the string str2
for i in range(M):
# Insert str1[i]
# into st1
st2.add(str2[i])
# If distinct characters in
# str1 and str2 are not same
if (st1 != st2):
return False
# Stores frequency of
# each character of str2
hash2 = [0] * 256
# Traverse the string str2
for i in range(M):
# Update frequency
# of str2[i]
hash2[ord(str2[i])] += 1
# Sort hash1[] array
hash1.sort()
# Sort hash2[] array
hash2.sort()
# Traverse hash1[] and hash2[]
for i in range(256):
# If hash1[i] not
# equal to hash2[i]
if (hash1[i] != hash2[i]):
return False
return True
# Driver Code
if __name__ == "__main__":
str1 = "xyyzzlll"
str2 = "yllzzxxx"
if (checkStr1CanConStr2(str1, str2)):
print("True")
else:
print("False")
# This code is contributed by chitranayal
C#
// C# program to implement
// the above approach
using System;
using System.Collections.Generic;
class GFG{
static bool checkStr1CanConStr2(String str1,
String str2)
{
// Stores length of str1
int N = str1.Length;
// Stores length of str2
int M = str2.Length;
// Stores distinct characters
// of str1
HashSet<int> st1 = new HashSet<int>();
// Stores distinct characters
// of str2
HashSet<int> st2 = new HashSet<int>();
// Stores frequency of
// each character of str1
int []hash1 = new int[256];
// Traverse the String str1
for (int i = 0; i < N; i++)
{
// Update frequency
// of str1[i]
hash1[str1[i]]++;
}
// Traverse the String str1
for (int i = 0; i < N; i++)
{
// Insert str1[i]
// into st1
st1.Add(str1[i]);
}
// Traverse the String str2
for (int i = 0; i < M; i++)
{
// Insert str1[i]
// into st1
st2.Add(str2[i]);
}
// If distinct characters in
// str1 and str2 are not same
if (st1.Equals(st2))
{
return false;
}
// Stores frequency of
// each character of str2
int []hash2 = new int[256];
// Traverse the String str2
for (int i = 0; i < M; i++)
{
// Update frequency
// of str2[i]
hash2[str2[i]]++;
}
// Sort hash1[] array
Array.Sort(hash1);
// Sort hash2[] array
Array.Sort(hash2);
// Traverse hash1[] and hash2[]
for (int i = 0; i < 256; i++)
{
// If hash1[i] not
// equal to hash2[i]
if (hash1[i] != hash2[i])
{
return false;
}
}
return true;
}
// Driver Code
public static void Main(String[] args)
{
String str1 = "xyyzzlll";
String str2 = "yllzzxxx";
if (checkStr1CanConStr2(str1, str2))
{
Console.Write("True");
}
else
{
Console.Write("False");
}
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// Javascript program to implement
// the above approach
function checkStr1CanConStr2(str1, str2)
{
// Stores length of str1
var N = str1.length;
// Stores length of str2
var M = str2.length;
// Stores distinct characters
// of str1
var st1 = new Set();
// Stores distinct characters
// of str2
var st2 = new Set();
// Stores frequency of
// each character of str1
var hash1 = Array(256).fill(0);
// Traverse the string str1
for (var i = 0; i < N; i++) {
// Update frequency
// of str1[i]
hash1[str1[i].charCodeAt(0)]++;
}
// Traverse the string str1
for (var i = 0; i < N; i++) {
// Insert str1[i]
// into st1
st1.add(str1[i]);
}
// Traverse the string str2
for (var i = 0; i < M; i++) {
// Insert str1[i]
// into st1
st2.add(str2[i]);
}
// If distinct characters in
// str1 and str2 are not same
if (st1.size != st2.size) {
return false;
}
// Stores frequency of
// each character of str2
var hash2 = Array(256).fill(0);
// Traverse the string str2
for (var i = 0; i < M; i++) {
// Update frequency
// of str2[i]
hash2[str2[i].charCodeAt(0)]++;
}
// Sort hash1[] array
hash1.sort((a,b)=>a-b);
hash2.sort((a,b)=>a-b);
// Traverse hash1[] and hash2[]
for (var i = 0; i < 256; i++) {
// If hash1[i] not
// equal to hash2[i]
if (hash1[i] != hash2[i]) {
return false;
}
}
return true;
}
// Driver Code
var str1 = "xyyzzlll";
var str2 = "yllzzxxx";
if (checkStr1CanConStr2(str1, str2)) {
document.write( "True");
}
else {
document.write( "False");
}
</script>
Producción:
True
Complejidad de Tiempo: O(N + M + 256)
Espacio Auxiliar: O(256)
Publicación traducida automáticamente
Artículo escrito por IshwarGupta y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA