Group Anagrams

Q: Quelle est la complexité temporelle du regroupement des anagrammes ?

La création des clés avec les lettres triées prend O(n · k log k) pour n mots de jusqu’à k lettres, et le travail sur la map est de O(n · k) . Trier les mots pour ordonner le résultat ajoute O(n · k · log n) , ce qui domine. L’espace requis est de O(n · k) pour les clés et les groupes.

MoyenHachage Tri

+10

Tu reçois une liste de mots strs. Deux mots sont des anagrammes lorsque l’un réarrange les lettres de l’autre, chacune étant utilisée le même nombre de fois. Regroupe chaque mot avec tous ses anagrammes et renvoie une chaîne par groupe : ses mots par ordre alphabétique, séparés par une seule espace. Trie les groupes par ordre alphabétique selon leur premier mot.

Un mot répété apparaît 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 joints 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 de l’alphabet anglais.

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 ont en commun les lettres e, n, o, s et t. apple ne correspond à rien et, en tant que premier mot, arrive en tête.

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, ils forment donc leur propre groupe. acre vient avant arc car c vient avant r à la deuxième lettre.

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

Pour aller plus loin

Si les mots pouvaient contenir n’importe quels caractères Unicode, quelle clé — les lettres triées ou le nombre de lettres — fonctionnerait toujours, et qu’est-ce que tu changerais ?

Indices

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

0 sur 3 ouverts

Solution

Calculez une clé à partir de chaque mot seul, identique pour tous ses anagrammes et différente pour tout autre mot. Les lettres d’un mot triées constituent une telle clé, et une table de hachage associant chaque clé à un groupe rassemble les mots en un seul passage. Triez d’abord les mots, et l’ordre requis sera obtenu sans effort supplémentaire.

Compare chaque mot à chaque groupe

Correcte, mais ne termine pas sur les plus gros tests

Intuition

Conservez une liste de groupes et comparez chaque mot au premier mot de chaque groupe. La relation d’anagramme est transitive : une seule comparaison par groupe suffit donc à déterminer l’appartenance. Deux mots sont des anagrammes lorsqu’ils ont la même longueur et le même nombre de chacune des 26 lettres. Triez d’abord l’entrée : chaque groupe se constitue alors dans l’ordre alphabétique, et les groupes sont créés dans l’ordre de leur premier mot.

Lorsqu’aucune paire de mots ne forme une anagramme, chaque mot est comparé à tous les groupes précédents : 4000 mots nécessitent environ 8 × 10^6 comparaisons, chacune portant sur jusqu’à 8 lettres et 26 compteurs.

Algorithme

Trie les mots par ordre alphabétique.
Pour chaque mot, trouve un groupe dont le premier mot a le même nombre de chaque lettre et ajoute le mot à ce groupe. Si aucun ne correspond, crée un nouveau groupe.
Renvoie les mots de chaque groupe, séparés par un seul espace, dans l’ordre de création.

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

Calculez le nom du groupe à partir du mot lui-même. Triez les lettres d’un mot, et chaque anagramme donne le même texte : listen, silent et enlist deviennent tous eilnst, tandis que stone devient enost. Deux mots ont exactement la même forme triée s’ils contiennent les mêmes lettres le même nombre de fois, ce qui est la définition d’une anagramme. Une table de hachage associant une clé à une liste de mots regroupe alors tout en un seul passage, sans qu’aucun mot soit comparé à un autre groupe.

L’ordre est déterminé en triant d’abord l’entrée, comme précédemment : chaque liste se remplit par ordre alphabétique, et une clé est ajoutée à la table lorsque le premier mot de son groupe arrive. Une table qui conserve l’ordre d’insertion renvoie les groupes dans cet ordre ; sinon, conservez les groupes dans une liste et associez chaque clé à son index.

Le tri de l’entrée nécessite environ 5 × 10^4 comparaisons de mots pour 4000 mots, au lieu de 8 × 10^6.

Algorithme

Trie les mots par ordre alphabétique.
Pour chaque mot, construis sa clé en triant ses lettres.
Recherche la clé dans une table de hachage. Si elle est nouvelle, crée un groupe vide pour celle-ci, en conservant les groupes dans l’ordre de leur création.
Ajoute le mot au groupe associé à sa clé.
Renvoie les mots de chaque groupe, séparés par un seul 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

Ordonner les groupes selon leur clé plutôt que selon le premier mot. Pour ["cab", "bad"], les clés abc et abd placent cab en premier, mais c’est bad qui devrait être en tête.
Collecter les mots dans un ensemble. ["b", "a", "b"] doit donner b b ; un ensemble ne conserve qu’une seule copie.
Construire une clé à partir des lettres distinctes uniquement. ab et aabb utilisent les deux mêmes lettres, mais ne sont pas des anagrammes.
Trier chaque groupe, mais pas l’entrée, et ne pas trier les groupes. L’ordre d’insertion suit alors l’entrée, et non les premiers mots.

Questions fréquentes3

Quelle est la complexité temporelle du regroupement des anagrammes ?

La création des clés avec les lettres triées prend O(n · k log k) pour n mots de jusqu’à k lettres, et le travail sur la map est de O(n · k). Trier les mots pour ordonner le résultat ajoute O(n · k · log n), ce qui domine. L’espace requis est de O(n · k) pour les clés et les groupes.

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

Une clé de comptage, les 26 nombres d’occurrences des lettres écrits sous forme de texte, comme 1#0#2#…, prend O(k) au lieu de O(k log k) : elle est donc plus performante pour les mots longs. Pour les mots de 8 lettres ou moins, le tri est tout aussi rapide. Les deux clés sont exactes : deux mots ont les mêmes nombres d’occurrences exactement lorsqu’ils ont les mêmes lettres triées.

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

Des lettres différentes peuvent donner le même total : a + d égale b + c, donc ad et bc seraient dans le même groupe. Un produit d’un nombre premier par lettre est exact, mais avec 101 pour z, un mot composé de dix z dépasse la capacité d’un entier sur 64 bits.

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

Test #1

Test #2

Test #3

Argument

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

Résultat attendu

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