Group Anagrams

+10

Vous obtenez une liste de mots strs. Deux mots sont des anagrammes lorsque l’un est une réorganisation de l’autre : les mêmes lettres, chacune utilisée le même nombre de fois. Regroupez chaque mot avec tous ses anagrammes, puis renvoyez une chaîne par groupe : les mots du groupe par ordre alphabétique, séparés par un seul espace. Triez les groupes par ordre alphabétique selon leur premier mot.

Un mot qui apparaît deux fois figure deux fois dans son groupe, et un mot sans anagramme forme un groupe à lui seul. L’ordre alphabétique correspond à l’ordre du dictionnaire : aab vient avant ab, et ab avant abc.

Fonction

groupAnagrams(strs: string-array) → string-array

strsstring-array: les mots à regrouper, uniquement des lettres minuscules
Renvoiestring-array: une chaîne par groupe : ses mots triés et reliés par des espaces, les groupes étant ordonnés selon leur premier mot

Contraintes

1 ≤ strs.length ≤ 4000
1 ≤ strs[i].length ≤ 8
Chaque mot ne contient que des lettres minuscules anglaises.

Exemples

Entrée: strs = ["listen", "stone", "silent", "notes", "enlist", "onset", "tones", "apple"]
Sortie: ["apple", "enlist listen silent", "notes onset stone tones"]
Explication: enlist, listen et silent utilisent chacun une fois les lettres e, i, l, n, s et t. notes, onset, stone et tones partagent les lettres e, n, o, s et t, et apple ne correspond à rien. En triant par premier mot, les groupes sont apple, enlist, notes.

Entrée: strs = ["race", "arc", "care", "car", "acre"]
Sortie: ["acre care race", "arc car"]
Explication: acre, care et race ont en commun les lettres a, c, e et r. arc et car n’ont pas de e, elles forment donc leur propre groupe. acre vient avant arc parce que c vient avant r à la deuxième lettre.

Entrée: strs = ["b", "a", "b"]
Sortie: ["a", "b b"]
Explication: Les deux copies de b sont des anagrammes l’une de l’autre, et toutes deux restent dans le groupe. a n’a pas de partenaire et vient en premier.

+15 tests cachés à la soumission

Pour aller plus loin

Supposons que les mots puissent contenir n’importe quels caractères Unicode au lieu de 26 lettres minuscules. Laquelle des deux clés, les lettres triées ou le nombre de lettres, fonctionne toujours, et qu’y changeriez-vous ?

Indices

Ouvrez-les un par un. Chacun en dévoile un peu plus.

0 sur 3 ouverts

Solution

Comparer chaque mot à tous les autres fonctionne, mais cela nécessite une comparaison complète pour chaque paire. La solution consiste à utiliser une clé canonique : une valeur que tu calcules à partir d’un seul mot, qui est identique pour toutes ses anagrammes et différente pour tous les autres mots. Les lettres d’un mot triées dans l’ordre constituent une telle clé, et une table de hachage qui associe chaque clé à un groupe permet d’effectuer le regroupement en un seul passage. L’ordre requis est obtenu automatiquement si tu tries les mots avant de les regrouper.

Comparez chaque mot à chaque groupe

Correcte, mais ne termine pas sur les plus gros tests

Intuition

La relation d’anagramme est transitive : si stone correspond à notes et notes correspond à tones, alors stone correspond à tones. Ainsi, un nouveau mot n’a jamais besoin de correspondre à chaque membre d’un groupe. Le comparer au premier mot du groupe permet de décider s’il en fait partie.

Pour comparer deux mots, comptez les lettres. Ce sont des anagrammes lorsqu’ils ont la même longueur et que chaque lettre apparaît autant de fois dans l’un que dans l’autre. Ajoutez 1 pour chaque lettre du premier mot et soustrayez 1 pour chaque lettre du second, puis vérifiez que les 26 compteurs se terminent tous à 0.

Triez d’abord l’entrée, et l’ordre se fera de lui-même. Les mots arrivent par ordre alphabétique, chacun rejoint la fin de son groupe, de sorte que chaque groupe reste trié. Un groupe est créé lorsque son premier mot dans l’ordre alphabétique arrive, donc les groupes sont déjà ordonnés selon leur premier mot.

Le coût vient du parcours. Lorsqu’aucune paire de mots n’est composée d’anagrammes, chaque mot est comparé à tous les groupes qui le précèdent : 4000 mots donnent environ 4000 × 3999 / 2 ≈ 8 × 10^6 comparaisons, chacune portant sur jusqu’à 8 lettres et 26 compteurs. C’est trop lent pour Python, Lua et R sur les tests les plus volumineux, et le travail augmente avec le carré de la taille de la liste, ce qui ferait échouer n’importe quel langage avec 10^5 mots.

Algorithme

Triez les mots par ordre alphabétique.
Conservez une liste de groupes, chacun étant une liste de mots.
Pour chaque mot, cherchez un groupe dont le premier mot a les mêmes fréquences de lettres, puis ajoutez-y le mot.
Si aucun groupe ne correspond, créez un nouveau groupe contenant uniquement ce mot.
Joignez les mots de chaque groupe avec des espaces simples et renvoyez les groupes dans l'ordre où vous les avez créés.

def is_anagram(a, b):
    # Same length, and every letter appears as often in a as in b.
    if len(a) != len(b):
        return False
    counts = [0] * 26
    for c in a:
        counts[ord(c) - 97] += 1
    for c in b:
        counts[ord(c) - 97] -= 1
    return all(x == 0 for x in counts)


def groupAnagrams(strs):
    # Sort first: each group fills up in alphabetical order,
    # and groups are created in the order of their first word.
    groups = []
    for word in sorted(strs):
        for group in groups:
            if is_anagram(group[0], word):
                group.append(word)
                break
        else:
            groups.append([word])
    return [" ".join(group) for group in groups]

Regrouper par lettres triées dans une table de hachage

Intuition

Au lieu de demander à quel groupe correspond un mot, calculez le nom du groupe à partir du mot lui-même. Triez les lettres d'un mot : toutes ses anagrammes donnent alors le même texte : listen, silent et enlist deviennent toutes eilnst, tandis que stone devient enost. Deux mots ont exactement la même forme triée lorsqu'ils contiennent les mêmes lettres le même nombre de fois, ce qui est la définition d'une anagramme. La forme triée constitue donc une clé canonique pour le groupe.

Une table de hachage associant chaque clé à une liste de mots regroupe alors tous les mots en un seul passage. Pour chaque mot, il faut effectuer un tri d'au plus 8 lettres et une recherche dans la table, sans jamais le comparer à un autre groupe.

Pour conserver l'ordre, triez l'entrée avant le regroupement, comme dans la première approche. Les mots arrivent par ordre alphabétique : chaque liste se remplit donc dans l'ordre, et une clé est ajoutée à la table lorsque le premier mot de son groupe arrive. Les tables qui préservent l'ordre d'insertion (un dict Python, une Map JavaScript, une LinkedHashMap Java, une map Dart, les hash Ruby et les tableaux PHP) renvoient les groupes dans cet ordre. Si la table ne garantit pas d'ordre, stockez dans la table l'indice de chaque groupe et conservez les groupes eux-mêmes dans une liste.

Le tri de l'entrée nécessite environ n log n comparaisons portant sur jusqu'à k lettres, soit environ 5 × 10^4 comparaisons de mots pour 4000 mots au lieu de 8 × 10^6. La construction des clés ajoute O(n · k log k), un coût faible en comparaison, car k ≤ 8.

Algorithme

Triez les mots par ordre alphabétique.
Pour chaque mot, construisez sa clé en triant ses lettres.
Recherchez la clé dans une table de hachage. Si elle est nouvelle, créez un groupe vide pour elle, en conservant les groupes dans l’ordre de leur création.
Ajoutez le mot au groupe associé à sa clé.
Renvoyez les mots de chaque groupe, séparés par une seule espace, les groupes étant dans l’ordre de leur création.

def groupAnagrams(strs):
    # Sort first: each group fills up in alphabetical order,
    # and groups are created in the order of their first word.
    groups = {}  # key (the letters in sorted order) -> the group's words
    for word in sorted(strs):
        key = "".join(sorted(word))
        groups.setdefault(key, []).append(word)
    # A dict keeps insertion order, so the groups come out by first word.
    return [" ".join(words) for words in groups.values()]

Pièges et cas limites

Le regroupement est la partie qu’on s’exerce à faire. La plupart des mauvaises réponses à cette version sont dues à l’ordre de sortie et aux clés qui ne sont pas uniques.

Trier les groupes selon leur clé au lieu de leur premier mot. Une clé est le plus petit réarrangement de ses lettres, et non l’un des mots : pour ["cab", "bad"], les clés sont abc et abd, ce qui placerait cab en premier, mais selon le premier mot, bad vient en premier.
Rassembler les mots dans un ensemble. ["b", "a", "b"] doit donner b b ; un ensemble ne conserve qu’une seule copie.
Une clé construite uniquement à partir des lettres distinctes. ab et aabb utilisent les deux mêmes lettres, mais aabb en contient deux de chaque, donc ce ne sont pas des anagrammes.
Une clé qui additionne les codes des lettres. ad et bc ont la même somme, donc une somme regroupe des mots qui n’ont aucune lettre en commun.
Trier chaque groupe, mais pas l’entrée, puis oublier de trier les groupes. L’ordre d’insertion est alors celui de l’entrée, et non celui des premiers mots.
Joindre les éléments à la main et laisser une espace au début ou à la fin de la chaîne d’un groupe.

Questions fréquentes4

Quelle est la complexité temporelle du regroupement des anagrammes ?

Avec une table de hachage indexée par les lettres triées, la construction des clés prend O(n · k log k) pour n mots de jusqu’à k lettres, et les opérations sur la table prennent O(n · k). Cette version trie également les mots pour ordonner le résultat, ce qui ajoute O(n · k · log n). L’espace requis est de O(n · k) pour les clés et les groupes.

Une clé de comptage des lettres est-elle plus rapide que le tri de chaque mot ?

Une clé de comptage, les 26 nombres de lettres écrits sous forme de texte, par exemple 1#0#2#…, prend un temps de O(k) au lieu de O(k log k) ; elle est donc plus efficace pour les mots longs. Pour les mots de 8 lettres au maximum, le tri est tout aussi rapide, et le tri alphabétique du résultat coûte plus cher que l’une ou l’autre clé. Les deux clés sont correctes, car deux mots ont les mêmes nombres de lettres exactement lorsqu’ils ont les mêmes lettres triées.

Pourquoi ne pas utiliser la somme des codes des lettres comme clé ?

Différentes lettres peuvent donner le même total : a + d est égal à b + c, donc ad et bc se retrouveraient dans un même groupe. Une clé doit être identique pour les anagrammes et différente pour tout le reste, et les lettres triées ou le décompte complet de chaque lettre le garantissent. Multiplier un nombre premier par lettre est également exact, mais avec 101 pour z, un mot composé de dix z déborde déjà un entier de 64 bits.

Pourquoi trier l’entrée avant de la regrouper ?

La réponse demande des groupes triés selon leur premier mot. Trier tous les mots une seule fois permet d’obtenir les deux résultats : chaque groupe reçoit ses mots par ordre alphabétique, et un groupe est créé lorsque son premier mot arrive. Trier ensuite chaque groupe, puis les groupes selon leur premier mot, donne le même résultat avec davantage de code.

Python

def groupAnagrams(strs):
    # Écrivez le code ici

Cas de test

Cas 1

Cas 2

Cas 3

Entrée

strs = ["listen", "stone", "silent", "notes", "enlist", "onset", "tones", "apple"]

Attendu

["apple", "enlist listen silent", "notes onset stone tones"]