Escriba una función para verificar si dos strings dadas son una permutación entre sí o no. Una permutación de una string es otra string que contiene los mismos caracteres, solo el orden de los caracteres puede ser diferente. Por ejemplo, «abcd» y «dabc» son permutaciones entre sí.
Le recomendamos encarecidamente que haga clic aquí y lo practique antes de pasar a la solución.
Método 1 (Usar clasificación)
1) Ordenar ambas strings
2) Comparar las strings ordenadas
C++
// C++ program to check whether two strings are
// Permutations of each other
#include <bits/stdc++.h>
using namespace std;
/* function to check whether two strings are
Permutation of each other */
bool arePermutation(string str1, string str2)
{
// Get lengths of both strings
int n1 = str1.length();
int n2 = str2.length();
// If length of both strings is not same,
// then they cannot be Permutation
if (n1 != n2)
return false;
// Sort both strings
sort(str1.begin(), str1.end());
sort(str2.begin(), str2.end());
// Compare sorted strings
for (int i = 0; i < n1; i++)
if (str1[i] != str2[i])
return false;
return true;
}
/* Driver program to test to print printDups*/
int main()
{
string str1 = "test";
string str2 = "ttew";
if (arePermutation(str1, str2))
printf("Yes");
else
printf("No");
return 0;
}
Java
// Java program to check whether two strings are
// Permutations of each other
import java.util.*;
class GfG {
/* function to check whether two strings are
Permutation of each other */
static boolean arePermutation(String str1, String str2)
{
// Get lengths of both strings
int n1 = str1.length();
int n2 = str2.length();
// If length of both strings is not same,
// then they cannot be Permutation
if (n1 != n2)
return false;
char ch1[] = str1.toCharArray();
char ch2[] = str2.toCharArray();
// Sort both strings
Arrays.sort(ch1);
Arrays.sort(ch2);
// Compare sorted strings
for (int i = 0; i < n1; i++)
if (ch1[i] != ch2[i])
return false;
return true;
}
/* Driver program to test to print printDups*/
public static void main(String[] args)
{
String str1 = "test";
String str2 = "ttew";
if (arePermutation(str1, str2))
System.out.println("Yes");
else
System.out.println("No");
}
}
Python3
# Python3 program to check whether two
# strings are Permutations of each other
# function to check whether two strings
# are Permutation of each other */
def arePermutation(str1, str2):
# Get lengths of both strings
n1 = len(str1)
n2 = len(str2)
# If length of both strings is not same,
# then they cannot be Permutation
if (n1 != n2):
return False
# Sort both strings
a = sorted(str1)
str1 = " ".join(a)
b = sorted(str2)
str2 = " ".join(b)
# Compare sorted strings
for i in range(0, n1, 1):
if (str1[i] != str2[i]):
return False
return True
# Driver Code
if __name__ == '__main__':
str1 = "test"
str2 = "ttew"
if (arePermutation(str1, str2)):
print("Yes")
else:
print("No")
# This code is contributed by
# Sahil_Shelangia
C#
// C# program to check whether two strings are
// Permutations of each other
using System;
class GfG
{
/* function to check whether two strings are
Permutation of each other */
static bool arePermutation(String str1, String str2)
{
// Get lengths of both strings
int n1 = str1.Length;
int n2 = str2.Length;
// If length of both strings is not same,
// then they cannot be Permutation
if (n1 != n2)
return false;
char []ch1 = str1.ToCharArray();
char []ch2 = str2.ToCharArray();
// Sort both strings
Array.Sort(ch1);
Array.Sort(ch2);
// Compare sorted strings
for (int i = 0; i < n1; i++)
if (ch1[i] != ch2[i])
return false;
return true;
}
/* Driver code*/
public static void Main(String[] args)
{
String str1 = "test";
String str2 = "ttew";
if (arePermutation(str1, str2))
Console.WriteLine("Yes");
else
Console.WriteLine("No");
}
}
// This code contributed by Rajput-Ji
Javascript
<script>
// Javascript program to check whether two
// strings are Permutations of each other
// Function to check whether two strings are
// Permutation of each other
function arePermutation(str1, str2)
{
// Get lengths of both strings
let n1 = str1.length;
let n2 = str2.length;
// If length of both strings is not same,
// then they cannot be Permutation
if (n1 != n2)
return false;
let ch1 = str1.split(' ');
let ch2 = str2.split(' ');
// Sort both strings
ch1.sort();
ch2.sort();
// Compare sorted strings
for(let i = 0; i < n1; i++)
if (ch1[i] != ch2[i])
return false;
return true;
}
// Driver Code
let str1 = "test";
let str2 = "ttew";
if (arePermutation(str1, str2))
document.write("Yes");
else
document.write("No");
// This code is contributed by suresh07
</script>
Producción:
No
Complejidad de tiempo: La complejidad de tiempo de este método depende de la técnica de clasificación utilizada. En la implementación anterior, se utiliza quickSort, que puede ser O(n^2) en el peor de los casos. Si usamos un algoritmo de clasificación O(nLogn) como la clasificación por combinación, entonces la complejidad se convierte en O(nLogn)
Espacio auxiliar: O(1).
Método 2 (Contar caracteres)
Este método asume que el conjunto de posibles caracteres en ambas strings es pequeño. En la siguiente implementación, se supone que los caracteres se almacenan utilizando 8 bits y puede haber 256 caracteres posibles.
1) Cree arrays de conteo de tamaño 256 para ambas strings. Inicialice todos los valores en las arrays de conteo como 0.
2) Repita cada carácter de ambas strings e incremente el conteo de caracteres en las arrays de conteo correspondientes.
3) Comparar arrays de conteo. Si ambas arrays de conteo son iguales, devuelva verdadero.
C++
// C++ program to check whether two strings are
// Permutations of each other
#include <bits/stdc++.h>
using namespace std;
# define NO_OF_CHARS 256
/* function to check whether two strings are
Permutation of each other */
bool arePermutation(string str1, string str2)
{
// Create 2 count arrays and initialize
// all values as 0
int count1[NO_OF_CHARS] = {0};
int count2[NO_OF_CHARS] = {0};
int i;
// For each character in input strings,
// increment count in the corresponding
// count array
for (i = 0; str1[i] && str2[i]; i++)
{
count1[str1[i]]++;
count2[str2[i]]++;
}
// If both strings are of different length.
// Removing this condition will make the
// program fail for strings like "aaca"
// and "aca"
if (str1[i] || str2[i])
return false;
// Compare count arrays
for (i = 0; i < NO_OF_CHARS; i++)
if (count1[i] != count2[i])
return false;
return true;
}
/* Driver program to test to print printDups*/
int main()
{
string str1 = "geeksforgeeks";
string str2 = "forgeeksgeeks";
if ( arePermutation(str1, str2) )
printf("Yes");
else
printf("No");
return 0;
}
Java
// JAVA program to check if two strings
// are Permutations of each other
import java.io.*;
import java.util.*;
class GFG{
static int NO_OF_CHARS = 256;
/* function to check whether two strings
are Permutation of each other */
static boolean arePermutation(char str1[], char str2[])
{
// Create 2 count arrays and initialize
// all values as 0
int count1[] = new int [NO_OF_CHARS];
Arrays.fill(count1, 0);
int count2[] = new int [NO_OF_CHARS];
Arrays.fill(count2, 0);
int i;
// For each character in input strings,
// increment count in the corresponding
// count array
for (i = 0; i <str1.length && i < str2.length ;
i++)
{
count1[str1[i]]++;
count2[str2[i]]++;
}
// If both strings are of different length.
// Removing this condition will make the program
// fail for strings like "aaca" and "aca"
if (str1.length != str2.length)
return false;
// Compare count arrays
for (i = 0; i < NO_OF_CHARS; i++)
if (count1[i] != count2[i])
return false;
return true;
}
/* Driver program to test to print printDups*/
public static void main(String args[])
{
char str1[] = ("geeksforgeeks").toCharArray();
char str2[] = ("forgeeksgeeks").toCharArray();
if ( arePermutation(str1, str2) )
System.out.println("Yes");
else
System.out.println("No");
}
}
// This code is contributed by Nikita Tiwari.
Python
# Python program to check if two strings are # Permutations of each other NO_OF_CHARS = 256 # Function to check whether two strings are # Permutation of each other def arePermutation(str1, str2): # Create two count arrays and initialize # all values as 0 count1 = [0] * NO_OF_CHARS count2 = [0] * NO_OF_CHARS # For each character in input strings, # increment count in the corresponding # count array for i in str1: count1[ord(i)]+=1 for i in str2: count2[ord(i)]+=1 # If both strings are of different length. # Removing this condition will make the # program fail for strings like # "aaca" and "aca" if len(str1) != len(str2): return 0 # Compare count arrays for i in xrange(NO_OF_CHARS): if count1[i] != count2[i]: return 0 return 1 # Driver program to test the above functions str1 = "geeksforgeeks" str2 = "forgeeksgeeks" if arePermutation(str1, str2): print "Yes" else: print "No" # This code is contributed by Bhavya Jain
C#
// C# program to check if two strings
// are Permutations of each other
using System;
class GFG{
static int NO_OF_CHARS = 256;
/* function to check whether two strings
are Permutation of each other */
static bool arePermutation(char []str1, char []str2)
{
// Create 2 count arrays and initialize
// all values as 0
int []count1 = new int [NO_OF_CHARS];
int []count2 = new int [NO_OF_CHARS];
int i;
// For each character in input strings,
// increment count in the corresponding
// count array
for (i = 0; i <str1.Length && i < str2.Length ;
i++)
{
count1[str1[i]]++;
count2[str2[i]]++;
}
// If both strings are of different length.
// Removing this condition will make the program
// fail for strings like "aaca" and "aca"
if (str1.Length != str2.Length)
return false;
// Compare count arrays
for (i = 0; i < NO_OF_CHARS; i++)
if (count1[i] != count2[i])
return false;
return true;
}
/* Driver code*/
public static void Main(String []args)
{
char []str1 = ("geeksforgeeks").ToCharArray();
char []str2 = ("forgeeksgeeks").ToCharArray();
if ( arePermutation(str1, str2) )
Console.WriteLine("Yes");
else
Console.WriteLine("No");
}
}
// This code has been contributed by 29AjayKumar
Javascript
<script>
// Javascript program to check if two strings
// are Permutations of each other
let NO_OF_CHARS = 256;
/* Function to check whether two strings
are Permutation of each other */
function arePermutation(str1, str2)
{
// Create 2 count arrays and initialize
// all values as 0
let count1 = Array(NO_OF_CHARS);
let count2 = Array(NO_OF_CHARS);
count1.fill(0);
count2.fill(0);
let i;
// For each character in input strings,
// increment count in the corresponding
// count array
for(i = 0;
i < str1.length && i < str2.length;
i++)
{
count1[str1[i]]++;
count2[str2[i]]++;
}
// If both strings are of different length.
// Removing this condition will make the program
// fail for strings like "aaca" and "aca"
if (str1.length != str2.length)
return false;
// Compare count arrays
for(i = 0; i < NO_OF_CHARS; i++)
if (count1[i] != count2[i])
return false;
return true;
}
// Driver code
let str1 = ("geeksforgeeks").split('');
let str2 = ("forgeeksgeeks").split('');
if (arePermutation(str1, str2) )
document.write("Yes");
else
document.write("No");
// This code is contributed by rameshtravel07
</script>
Producción:
Yes
Complejidad de tiempo: O(n)
Espacio auxiliar: O(n).
La implementación anterior puede ser adicional para usar solo una array de conteo en lugar de dos. Podemos incrementar el valor en la array de conteo para caracteres en str1 y disminuir para caracteres en str2. Finalmente, si todos los valores de conteo son 0, entonces las dos strings se permutan entre sí. Gracias a Ace por sugerir esta optimización.
C++
// C++ function to check whether two strings are
// Permutations of each other
bool arePermutation(string str1, string str2)
{
// Create a count array and initialize all
// values as 0
int count[NO_OF_CHARS] = {0};
int i;
// For each character in input strings,
// increment count in the corresponding
// count array
for (i = 0; str1[i] && str2[i]; i++)
{
count[str1[i]]++;
count[str2[i]]--;
}
// If both strings are of different length.
// Removing this condition will make the
// program fail for strings like "aaca" and
// "aca"
if (str1[i] || str2[i])
return false;
// See if there is any non-zero value in
// count array
for (i = 0; i < NO_OF_CHARS; i++)
if (count[i])
return false;
return true;
}
Java
// Java function to check whether two strings are
// Permutations of each other
static boolean arePermutation(char str1[], char str2[])
{
// Create a count array and initialize all
// values as 0
int count[] = new int[NO_OF_CHARS];
int i;
// For each character in input strings,
// increment count in the corresponding
// count array
for (i = 0; str1[i] && str2[i]; i++)
{
count[str1[i]]++;
count[str2[i]]--;
}
// If both strings are of different length.
// Removing this condition will make the
// program fail for strings like "aaca" and
// "aca"
if (str1[i] || str2[i])
return false;
// See if there is any non-zero value in
// count array
for (i = 0; i < NO_OF_CHARS; i++)
if (count[i] != 0)
return false;
return true;
}
// This code is contributed by divyesh072019.
Python3
# Python3 function to check whether two strings are # Permutations of each other def arePermutation(str1, str2): # Create a count array and initialize all # values as 0 count = [0 for i in range(NO_OF_CHARS)] i = 0 # For each character in input strings, # increment count in the corresponding # count array while(str1[i] and str2[i]): count[str1[i]] += 1 count[str2[i]] -= 1 # If both strings are of different length. # Removing this condition will make the # program fail for strings like "aaca" and # "aca" if (str1[i] or str2[i]): return False; # See if there is any non-zero value in # count array for i in range(NO_OF_CHARS): if (count[i]): return False; return True; # This code is contributed by pratham76.
C#
// C# function to check whether two strings are
// Permutations of each other
static bool arePermutation(char[] str1, char[] str2)
{
// Create a count array and initialize all
// values as 0
int[] count = new int[NO_OF_CHARS];
int i;
// For each character in input strings,
// increment count in the corresponding
// count array
for (i = 0; str1[i] && str2[i]; i++)
{
count[str1[i]]++;
count[str2[i]]--;
}
// If both strings are of different length.
// Removing this condition will make the
// program fail for strings like "aaca" and
// "aca"
if (str1[i] || str2[i])
return false;
// See if there is any non-zero value in
// count array
for (i = 0; i < NO_OF_CHARS; i++)
if (count[i] != 0)
return false;
return true;
}
// This code is contributed by divyeshrabadiya07.
Javascript
<script>
// Javascript function to check whether two strings are
// Permutations of each other
function arePermutation(str1,str2)
{
// Create a count array and initialize all
// values as 0
let count = new Array(NO_OF_CHARS);
let i;
// For each character in input strings,
// increment count in the corresponding
// count array
for (i = 0; str1[i] && str2[i]; i++)
{
count[str1[i]]++;
count[str2[i]]--;
}
// If both strings are of different length.
// Removing this condition will make the
// program fail for strings like "aaca" and
// "aca"
if (str1[i] || str2[i])
return false;
// See if there is any non-zero value in
// count array
for (i = 0; i < NO_OF_CHARS; i++)
if (count[i] != 0)
return false;
return true;
}
// This code is contributed by patel2127
</script>
Si el posible conjunto de caracteres contiene solo alfabetos en inglés, entonces podemos reducir el tamaño de las arrays a 58 y usar str[i] – ‘A’ como índice para contar arrays porque el valor ASCII de ‘A’ es 65, ‘B’ es 66, ….., Z es 90 y ‘a’ es 97, ‘b’ es 98, ……, ‘z’ es 122. Esto optimizará aún más este método.
Complejidad de tiempo: O(n)
Espacio auxiliar: O(n).
Sugiera si alguien tiene una mejor solución que sea más eficiente en términos de espacio y tiempo.
Este artículo es una contribución de Aarti_Rathi . Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.