Dada una array de strings, la tarea es eliminar las strings que son un anagrama de una string anterior y luego imprimir la array restante en orden.
Ejemplos:
Entrada: arr[] = { “geeks”, “keegs”, “code”, “doce” }, N = 4
Salida: [“code”, “geeks”]
Explicación:
“geeks” y “keegs” son anagramas, por lo que eliminamos «keegs».
Del mismo modo, «código» y «doce» son anagramas, por lo que eliminamos «doce».Entrada: arr[] = {“té”, “ate”, “anagrama”, “comer”, “gramaan”}, N = 5
Salida: [“anagrama”, “té”]
Explicación: “ate” y “comer ” son anagramas de “té”.
“gramaan” es un anagrama de “anagrama”, por lo tanto, array se convierte en [“anagrama”, “té”].
Enfoque: Para verificar si las dos strings dadas son anagramas o no lo son , simplemente podemos ordenar ambas strings y compararlas. Además, para verificar si se ha producido una string o no, podemos usar un hashmap .
- Cree una array auxiliar para mantener las strings resultantes y un hashmap para mantener una marca de la string que hemos encontrado hasta ahora.
- Luego itere a través de la string de array dada, ordene la string actual y verifique esa string en el mapa hash.
- Si la string actual no se encuentra en el mapa hash, presione arr[i] en la array resultante e inserte la string ordenada en el mapa hash.
- Finalmente, ordene la array resultante e imprima cada string.
A continuación se muestra la implementación del enfoque anterior.
C++
// C++ implementation to remove
// all the anagram strings
#include <bits/stdc++.h>
using namespace std;
// Function to remove the anagram string
void removeAnagrams(string arr[], int N)
{
// vector to store the final result
vector<string> ans;
// data structure to keep a mark
// of the previously occurred string
unordered_set<string> found;
for (int i = 0; i < N; i++) {
string word = arr[i];
// Sort the characters
// of the current string
sort(begin(word), end(word));
// Check if current string is not
// present inside the hashmap
// Then push it in the resultant vector
// and insert it in the hashmap
if (found.find(word) == found.end()) {
ans.push_back(arr[i]);
found.insert(word);
}
}
// Sort the resultant vector of strings
sort(begin(ans), end(ans));
// Print the required array
for (int i = 0; i < ans.size(); ++i) {
cout << ans[i] << " ";
}
}
// Driver code
int main()
{
string arr[]
= { "geeks", "keegs",
"code", "doce" };
int N = 4;
removeAnagrams(arr, N);
return 0;
}
Java
// Java implementation to remove
// all the anagram Strings
import java.util.*;
class GFG{
// Function to remove the anagram String
static void removeAnagrams(String arr[], int N)
{
// vector to store the final result
Vector<String> ans = new Vector<String>();
// data structure to keep a mark
// of the previously occurred String
HashSet<String> found = new HashSet<String> ();
for (int i = 0; i < N; i++) {
String word = arr[i];
// Sort the characters
// of the current String
word = sort(word);
// Check if current String is not
// present inside the hashmap
// Then push it in the resultant vector
// and insert it in the hashmap
if (!found.contains(word)) {
ans.add(arr[i]);
found.add(word);
}
}
// Sort the resultant vector of Strings
Collections.sort(ans);
// Print the required array
for (int i = 0; i < ans.size(); ++i) {
System.out.print(ans.get(i)+ " ");
}
}
static String sort(String inputString)
{
// convert input string to char array
char tempArray[] = inputString.toCharArray();
// sort tempArray
Arrays.sort(tempArray);
// return new sorted string
return new String(tempArray);
}
// Driver code
public static void main(String[] args)
{
String arr[]
= { "geeks", "keegs",
"code", "doce" };
int N = 4;
removeAnagrams(arr, N);
}
}
// This code is contributed by 29AjayKumar
Python3
# Python3 implementation to remove # all the anagram strings # Function to remove the anagram string def removeAnagrams(arr, N): # vector to store the final result ans = [] # data structure to keep a mark # of the previously occurred string found = dict() for i in range(N): word = arr[i] # Sort the characters # of the current string word = " ".join(sorted(word)) # Check if current is not # present inside the hashmap # Then push it in the resultant vector # and insert it in the hashmap if (word not in found): ans.append(arr[i]) found[word] = 1 # Sort the resultant vector of strings ans = sorted(ans) # Print the required array for i in range(len(ans)): print(ans[i], end=" ") # Driver code if __name__ == '__main__': arr=["geeks", "keegs","code", "doce"] N = 4 removeAnagrams(arr, N) # This code is contributed by mohit kumar 29
C#
// C# implementation to remove
// all the anagram Strings
using System;
using System.Collections.Generic;
class GFG{
// Function to remove the anagram String
static void removeAnagrams(String []arr, int N)
{
// vector to store the readonly result
List<String> ans = new List<String>();
// data structure to keep a mark
// of the previously occurred String
HashSet<String> found = new HashSet<String> ();
for (int i = 0; i < N; i++) {
String word = arr[i];
// Sort the characters
// of the current String
word = sort(word);
// Check if current String is not
// present inside the hashmap
// Then push it in the resultant vector
// and insert it in the hashmap
if (!found.Contains(word)) {
ans.Add(arr[i]);
found.Add(word);
}
}
// Sort the resultant vector of Strings
ans.Sort();
// Print the required array
for (int i = 0; i < ans.Count; ++i) {
Console.Write(ans[i]+ " ");
}
}
static String sort(String inputString)
{
// convert input string to char array
char []tempArray = inputString.ToCharArray();
// sort tempArray
Array.Sort(tempArray);
// return new sorted string
return String.Join("",tempArray);
}
// Driver code
public static void Main(String[] args)
{
String []arr
= { "geeks", "keegs",
"code", "doce" };
int N = 4;
removeAnagrams(arr, N);
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// Javascript implementation to remove
// all the anagram Strings
// Function to remove the anagram String
function removeAnagrams(arr, N)
{
// Vector to store the final result
let ans = [];
// Data structure to keep a mark
// of the previously occurred String
let found = new Set();
for(let i = 0; i < N; i++)
{
let word = arr[i];
// Sort the characters
// of the current String
word = sort(word);
// Check if current String is not
// present inside the hashmap
// Then push it in the resultant vector
// and insert it in the hashmap
if (!found.has(word))
{
ans.push(arr[i]);
found.add(word);
}
}
// Sort the resultant vector of Strings
(ans).sort();
// Print the required array
for(let i = 0; i < ans.length; ++i)
{
document.write(ans[i] + " ");
}
}
function sort(inputString)
{
// Convert input string to char array
let tempArray = inputString.split("");
// Sort tempArray
(tempArray).sort();
// Return new sorted string
return (tempArray).join("");
}
// Driver code
let arr = [ "geeks", "keegs",
"code", "doce" ];
let N = 4;
removeAnagrams(arr, N);
// This code is contributed by unknown2108
</script>
Producción:
code geeks
Complejidad de tiempo: O(n*mlogm) donde n es el tamaño de la array y m es la longitud de la palabra.
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.
Publicación traducida automáticamente
Artículo escrito por Sanjit_Prasad y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA