Group Anagrams

Description

[EN]

Given an array of strings strs, group all anagrams together into sublists. You may return the output in any order. An anagram is a string that contains the exact same characters as another string, but the order of the characters can be different.

Constraints:

• 1 <= strs.length <= 1000.

• 0 <= strs[i].length <= 100

• strs[i] is made up of lowercase English letters.

[FR]

Étant donné un tableau de chaînes de caractères strs, regroupez tous les anagrammes ensemble dans des sous-listes. Vous pouvez retourner le résultat dans n'importe quel ordre. Un anagramme est une chaîne de caractères qui contient exactement les mêmes lettres qu'une autre chaîne, mais dans un ordre différent.

Contraintes :

• 1 <= strs.length <= 1000 

• 0 <= strs[i].length <= 100

• strs[i] est composé uniquement de lettres minuscules de l'alphabet anglais.

Approche: Utilisation d'une HashMap la fréquence des lettres comme clé

• Pour chaque chaîne dans le tableau d'entrée, nous créons un tableau de taille 26 qui représente le nombre d'occurrences de chaque lettre de l'alphabet (de 'a' à 'z').

• Le tableau de fréquence est ensuite converti en une chaîne de caractères unique grâce à la méthode Arrays.toString(). Cette clé permet d'identifier les chaînes qui sont des anagrammes. Toutes ces chaînes auront la même clé, car elles contiennent les mêmes lettres avec les mêmes fréquences.

• J'utilise une HashMap où :

  • La clé est le tableau de fréquence converti en chaîne de caractères.

  • La valeur est une liste de chaînes qui partagent la même clé.

  Chaque fois qu'une chaîne a la même clé qu'une autre chaîne déjà rencontrée, elle est ajoutée à la même liste.

• Finalement, nous retournons les valeurs de la HashMap sous forme de liste de listes.

• Complexité temporelle: O(n*m) où m est le nombre de chaînes de caractères et n est la taille de la plus longue chaîne de caractères

• Complexité spatiale: O(m)