Escriba una función para verificar si dos strings dadas son un anagrama entre sí o no. Un anagrama 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 un anagrama el uno del otro.
Enfoque: el mapa desordenado también se puede usar para encontrar si dos strings dadas son anagramas o no. La idea es almacenar cada carácter de la primera string en el mapa, con su frecuencia como valor, y luego verificar cada carácter de la segunda string en el mapa, y si el carácter se encuentra en el mapa, reducir su valor de frecuencia. del mapa Si la frecuencia de un carácter se convierte en 0, bórrelo del mapa y, por último, si el mapa queda vacío, eso significa que todos los caracteres de la primera string están en la segunda string con el mismo número de ocurrencias (frecuencia de cada carácter) . Implementación:
CPP
// C++ program to check whether
// two strings are anagrams of
// each other or not, using Hashmap
#include <bits/stdc++.h>
#include <unordered_map>
using namespace std;
// Function to check whether two strings
// are an anagram of each other
bool isanagram(string s1, string s2)
{
int l1 = s1.length();
int l2 = s2.length();
unordered_map<char, int> m;
if (l1 != l2) {
return false;
}
for (int i = 0; i < l1; i++) {
m[s1[i]]++;
}
for (int i = 0; i < l2; i++) {
if (m.find(s2[i]) == m.end()) {
return false;
}
else {
m[s2[i]]--;
if (m[s2[i]] == 0) {
m.erase(s2[i]);
}
}
}
return m.size() == 0;
}
// Test function
void test(string str1, string str2)
{
cout << "Strings to be checked:\n"
<< str1 << "\n"
<< str2 << "\n";
if (isanagram(str1, str2)) {
cout << "The two strings are"
<< "anagram of each other\n";
}
else {
cout << "The two strings are not"
<< " anagram of each other\n";
}
cout << endl;
}
// Driver program
int main()
{
// Get the Strings
string str1 = "geeksforgeeks";
string str2 = "forgeeksgeeks";
// Test the Strings
test(str1, str2);
// Get the Strings
str1 = "geeksforgeeks";
str2 = "geeks";
// Test the Strings
test(str1, str2);
return 0;
}
Strings to be checked: geeksforgeeks forgeeksgeeks The two strings areanagram of each other Strings to be checked: geeksforgeeks geeks The two strings are not anagram of each other
Complejidad de tiempo: O(l1 + l2) donde l1 y l2 son longitudes de strings.
Espacio auxiliar: O(m1 + m2) donde m1 y m2 son números de caracteres únicos en cada string.
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.
Artículos relacionados:
- Compruebe si dos strings son anagramas entre sí
- Verifique si dos strings son anagramas entre sí usando HashMap en Java
Publicación traducida automáticamente
Artículo escrito por mishrakishan1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA