Compte tenu d'une matrice de cordes, retournez tous les groupes de chaînes qui sont des anagrammes

Utilisez Compter Trier pour trier le mot afin que le tri peut être effectué dans O (m). Après le tri générant la clé de Word et insérez un nœud (touche, valeur) dans HASHTABLE. La clé de génération peut être réalisée dans O (m).

Vous pouvez prendre de la valeur (clé, valeur) comme une matrice dynamique pouvant contenir plus d'une chaîne. Chaque fois que vous insérez une clé qui est déjà présente, appuyez simplement sur le mot d'origine à partir de laquelle la clé est générée sur une matrice de valeur.

Complexité de temps globale si (mn) où n est le nombre total de mots (taille de l'entrée).

Ce lien a également une solution à des problèmes similaires-> http://yourbitsandbytes.com/viewtopic.php?f=10&t=42

Nous définissons un alphabet, qui contient chaque lettre que nous pourrions avoir dans notre wordlist. Ensuite, nous avons besoin d'une prime différente pour chacune des lettres de l'alphabet, je recommande d'utiliser le plus petit que vous pouvez trouver.

qui nous donnerait la cartographie suivante: {a => 2, b => 3, c => 5, d => 7, etc}

comptez maintenant les lettres du mot que vous souhaitez représenter comme entier et construire votre integer entier comme entier. Suit:

pseudocode: xxx

Quelques exemples:

AAAA => 2 ^ 4

AABB => 2 ^ 2 * 3 ^ 2 = bbaa = baba = ...

et ainsi de suite.

Vous aurez donc un entier représentant chaque mot dans votre dictionnaire et le mot Vous voulez vérifier sera capable d'être converti en un entier. Donc, si n est la taille de votre liste de mots et k est la taille du mot le plus long que cela prendra O (nk) pour construire votre nouveau dictionnaire et O (k) pour vérifier un nouveau mot.

Hackthissite. com a un défi de programmation qui est: donné un mot brouillé, regardez-le dans un dictionnaire pour voir si des anagrammes de celui-ci sont dans le dictionnaire. Il y a un Bon article sur une solution efficace au problème à partir duquel j'ai emprunté la réponse, elle entre également dans détail sur d'autres optimisations.

#include <map>
#include <iostream>
#include <set>
#include <algorithm>

int main () {
  std::string word;
  std::map<std::string, std::set<std::string>> anagrams;
  while(std::cin >> word) {
    std::string sortedWord(word);
    std::sort(sortedWord.begin(), sortedWord.end());
    anagrams[sortedWord].insert(word);
  }
  for(auto& pair : anagrams) {
    for(auto& word : pair.second) {
      std::cout << word << " ";
    }
    std::cout << "\n";
  }
}
I'll let someone who is better at big-O analysis than I am figure out the complexities.