Eliminar string que es un anagrama de una string anterior

Posted on by Rudeus Greyrat

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 . 

  1. Cree una array auxiliar para mantener las strings resultantes y un hashmap para mantener una marca de la string que hemos encontrado hasta ahora.
  2. Luego itere a través de la string de array dada, ordene la string actual y verifique esa string en el mapa hash.
  3. 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.
  4. 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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *