Je vois pas bien par quelle noeud au cerveau tu finis avec une map comme clé ? Ou un vector<int> en valeurs ?
La clé c'est la structure de représentation. Et les valeurs sont bien entendus les mots...
Je l'ai pourtant écrit noir sur blanc
Qui sera bien sûr de la forme std::map<representation, std::vector<std::string>>À terme, tu as une collection de map<représentation, mots anagrammes ayant cette représentation>.
Tu as un premier jet qui utilise un short pour chaque lettre : ok, mais on peut beaucoup mieux faire.
Déjà, une lettre sera jamais présente un nombre négatif de fois. Donc unsigned.
Ensuite, une lettre peut être présente... 10 fois au max dans un mot ? Mettons 10 pour simplifier.
La représentation ne sera rien de plus qu'un nombre à 26 chiffres. Les unités ? Ça s'appelle A. Les dizaines B, ... exactement de la même façon que tu comptes depuis toujours il me semble, ou juste comment fonctionne l'écriture d'un nombre en base 10. Et la base peut être adaptée.
Mais commençons avec cette base 10.
Un u64 max ça vaut 18,446,744,073,709,551,615. C'est 20 chiffres, donc on va en utiliser 19 pour être sûr (donc [a,s]).
Il en reste 8, que l'on peut rentrer dans un u32.
Et bien pour créer la représentation, il s'agit d'un bête parcours de la chaîne et d'opérations triviales.
À vue de nez :
Et personnellement je serais partisan de recréer un pow utilisant des entiers qui pourrait être plus performant et dont les résultats devrait être plus précis que celui du standard qui utilise des flottants.
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22 struct Repr { uint64_t a{0}; uint32_t b{0}; }; Repr Compute(const std::string& str) { Repr ret; for (char c : str) { if (c < 't') { uint64_t index = pow(10, c - 'a'); ret.a += index; } else { uint32_t index = pow(10, c - 't'); ret.b += index; } } return ret; }
Ou une fonction qui fait un gros switch pour chaque caractère et retourne directement le multiplier.
Partager