Group Anagrams

+10

Ti viene fornito un elenco di parole strs. Due parole sono anagrammi quando una è una permutazione dell’altra: hanno le stesse lettere, ciascuna usata lo stesso numero di volte. Inserisci ogni parola in un gruppo con tutti i suoi anagrammi e restituisci una stringa per gruppo: le parole del gruppo in ordine alfabetico, separate da singoli spazi. Ordina i gruppi alfabeticamente in base alla prima parola.

Una parola che compare due volte viene elencata due volte nel suo gruppo, mentre una parola senza anagrammi forma un gruppo composto da una sola parola. Per ordine alfabetico si intende l’ordine del dizionario: aab viene prima di ab, e ab prima di abc.

Funzione

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

strsstring-array: le parole da raggruppare, solo lettere minuscole
Restituiscestring-array: una stringa per gruppo: le sue parole ordinate e unite da spazi, gruppi ordinati in base alla loro prima parola

Vincoli

1 ≤ strs.length ≤ 4000
1 ≤ strs[i].length ≤ 8
Ogni parola contiene solo lettere minuscole inglesi.

Esempi

Input: strs = ["listen", "stone", "silent", "notes", "enlist", "onset", "tones", "apple"]
Output: ["apple", "enlist listen silent", "notes onset stone tones"]
Spiegazione: enlist, listen e silent usano ciascuna una volta le lettere e, i, l, n, s e t. notes, onset, stone e tones condividono le lettere e, n, o, s e t, e apple non corrisponde a nulla. In base alla prima parola, i gruppi sono apple, enlist, notes.

Input: strs = ["race", "arc", "care", "car", "acre"]
Output: ["acre care race", "arc car"]
Spiegazione: acre, care e race hanno in comune a, c, e e r. arc e car non hanno la e, quindi formano un gruppo a parte. acre viene prima di arc perché la c viene prima della r nella seconda lettera.

Input: strs = ["b", "a", "b"]
Output: ["a", "b b"]
Spiegazione: Le due copie di b sono anagrammi l'una dell'altra e restano entrambe nel gruppo. a non ha un compagno e viene prima.

+15 test nascosti all’invio

Per approfondire

Supponiamo che le parole possano contenere qualsiasi carattere Unicode invece di 26 lettere minuscole. Quale delle due chiavi, le lettere ordinate o il conteggio delle lettere, continua a funzionare e cosa cambieresti?

Suggerimenti

Aprili uno alla volta. Ognuno rivela un po’ di più.

0 di 3 aperti

Soluzione

Confrontare ogni parola con tutte le altre funziona, ma richiede un confronto completo per ogni coppia. La soluzione al problema è una chiave canonica: un valore che calcoli usando una sola parola, uguale per tutti i suoi anagrammi e diverso per ogni altra parola. Le lettere di una parola in ordine alfabetico costituiscono una chiave di questo tipo, e una mappa hash che associa ogni chiave al relativo gruppo permette di raggruppare le parole in un solo passaggio. Se ordini le parole prima di raggrupparle, ottieni gratuitamente l’ordine richiesto.

Confronta ogni parola con ogni gruppo

Corretto, ma non termina sui test più grandi

Intuizione

Essere anagrammi è una relazione transitiva: se stone corrisponde a notes e notes corrisponde a tones, allora stone corrisponde a tones. Quindi una nuova parola non deve mai essere confrontata con ogni membro di un gruppo. Basta confrontarla con la prima parola del gruppo per decidere se ne fa parte.

Per confrontare due parole, conta le lettere. Sono anagrammi quando hanno la stessa lunghezza e ogni lettera compare lo stesso numero di volte in entrambe. Aggiungi 1 per ogni lettera della prima parola e sottrai 1 per ogni lettera della seconda, quindi controlla che tutti e 26 i contatori terminino a 0.

Ordina prima l'input e l'ordine si manterrà da sé. Le parole arrivano in ordine alfabetico e ognuna si aggiunge alla fine del proprio gruppo, così ogni gruppo rimane ordinato. Un gruppo viene creato quando arriva la sua prima parola in ordine alfabetico, quindi i gruppi sono già ordinati in base alla prima parola.

Il costo sta nella scansione. Quando non ci sono parole che sono anagrammi l'una dell'altra, ogni parola viene confrontata con tutti i gruppi precedenti: 4000 parole comportano circa 4000 × 3999 / 2 ≈ 8 × 10^6 confronti, ognuno dei quali esamina fino a 8 lettere e 26 contatori. È troppo lento per Python, Lua e R nei test più grandi, e il lavoro cresce con il quadrato della lista, quindi metterebbe in difficoltà qualsiasi linguaggio con 10^5 parole.

Algoritmo

Ordina le parole in ordine alfabetico.
Tieni un elenco di gruppi, ognuno composto da un elenco di parole.
Per ogni parola, cerca un gruppo la cui prima parola abbia lo stesso conteggio di lettere e aggiungi la parola al gruppo.
Se non trovi nessun gruppo corrispondente, avviane uno nuovo contenente solo questa parola.
Unisci le parole di ciascun gruppo con spazi singoli e restituisci i gruppi nell'ordine in cui li hai creati.

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]

Raggruppa per lettere ordinate in una mappa hash

Intuizione

Invece di chiederti a quale gruppo appartiene una parola, calcola il nome del gruppo a partire dalla parola stessa. Ordina le lettere di una parola e tutti i suoi anagrammi producono lo stesso testo: listen, silent ed enlist diventano tutti eilnst, mentre stone diventa enost. Due parole condividono esattamente la stessa forma ordinata quando contengono le stesse lettere lo stesso numero di volte: questa è la definizione di anagramma. Quindi, la forma ordinata è una chiave canonica per il gruppo.

Una mappa hash che associa ogni chiave a una lista di parole raggruppa tutto in un solo passaggio. Per ogni parola serve un ordinamento di al massimo 8 lettere e una ricerca nella mappa, e non viene mai confrontata con un altro gruppo.

Per mantenere l'ordine, ordina l'input prima di raggrupparlo, come nel primo approccio. Le parole arrivano in ordine alfabetico, quindi ogni lista si riempie in ordine e una chiave entra nella mappa quando arriva la prima parola del suo gruppo. Le mappe che mantengono l'ordine di inserimento (un dict Python, una Map JavaScript, una LinkedHashMap Java, una mappa Dart, gli hash Ruby e gli array PHP) restituiscono i gruppi in quell'ordine. Se la mappa non mantiene l'ordine, memorizza nella mappa l'indice di ogni gruppo e conserva i gruppi stessi in una lista.

Ordinare l'input richiede circa n log n confronti di al massimo k lettere, all'incirca 5 × 10^4 confronti tra parole per 4000 parole invece di 8 × 10^6. La creazione delle chiavi aggiunge O(n · k log k), un costo ridotto rispetto a quello precedente perché k ≤ 8.

Algoritmo

Ordina le parole alfabeticamente.
Per ogni parola, crea la sua chiave ordinandone le lettere.
Cerca la chiave in una mappa hash. Se è nuova, avvia un gruppo vuoto per essa, mantenendo i gruppi nell'ordine in cui li crei.
Aggiungi la parola al gruppo della sua chiave.
Restituisci le parole di ciascun gruppo unite da spazi singoli, con i gruppi nell'ordine di creazione.

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()]

Trappole e casi limite

Il raggruppamento è la parte su cui ci si esercita. La maggior parte delle risposte sbagliate in questa versione dipende dall’ordine dell’output e da chiavi non univoche.

Ordinare i gruppi in base alla loro chiave anziché alla prima parola. Una chiave è il riordinamento più piccolo delle sue parole, non una di esse: per ["cab", "bad"] le chiavi sono abc e abd, quindi cab verrebbe prima, ma in base alla prima parola viene prima bad.
Raccogliere le parole in un insieme. ["b", "a", "b"] deve dare b b; un insieme conserva una sola copia.
Una chiave costruita usando solo le lettere distinte. ab e aabb usano le stesse due lettere, ma aabb ne ha due per ciascuna, quindi non sono anagrammi.
Una chiave che somma i codici delle lettere. ad e bc hanno la stessa somma, quindi una somma raggruppa parole che non hanno lettere in comune.
Ordinare ogni gruppo ma non l’input, e poi dimenticare di ordinare i gruppi. L’ordine di inserimento è quindi quello dell’input, non quello delle prime parole.
Unire a mano e lasciare uno spazio all’inizio o alla fine della stringa di un gruppo.

Domande frequenti4

Qual è la complessità temporale di Group Anagrams?

Con una mappa hash indicizzata tramite lettere ordinate, la creazione delle chiavi richiede O(n · k log k) per n parole di al massimo k lettere, e il lavoro sulla mappa è O(n · k). Questa versione ordina anche le parole per ordinare l'output, aggiungendo O(n · k · log n). Lo spazio è O(n · k) per le chiavi e i gruppi.

Una chiave basata sul conteggio delle lettere è più veloce che ordinare ogni parola?

Una chiave di conteggio, ovvero i conteggi delle 26 lettere scritti come testo, ad esempio 1#0#2#…, richiede un tempo O(k) invece di O(k log k), quindi è più efficiente per le parole lunghe. Con parole di al massimo 8 lettere, l’ordinamento è altrettanto veloce e l’ordinamento alfabetico dell’output costa più di entrambe le chiavi. Entrambe le chiavi sono corrette, perché due parole hanno gli stessi conteggi esattamente quando hanno le stesse lettere ordinate.

Perché non usare la somma dei codici delle lettere come chiave?

Lettere diverse possono sommarsi allo stesso totale: a + d è uguale a b + c, quindi ad e bc finirebbero nello stesso gruppo. Una chiave deve essere uguale per gli anagrammi e diversa per tutto il resto, e le lettere ordinate o il conteggio completo di ogni lettera lo garantiscono. Moltiplicare un numero primo per ogni lettera è altrettanto preciso, ma con 101 per z, una parola composta da dieci z va già in overflow con un intero a 64 bit.

Perché ordinare l'input prima di raggrupparlo?

La risposta richiede gruppi ordinati in base alla loro prima parola. Ordinare tutte le parole una sola volta soddisfa entrambe le richieste: ogni gruppo riceve le proprie parole in ordine alfabetico e un gruppo viene creato quando arriva la sua prima parola. Ordinare successivamente ogni gruppo e poi i gruppi in base alla loro prima parola dà lo stesso risultato con più codice.

Python

def groupAnagrams(strs):
    # Scrivi il codice qui

Casi di test

Caso 1

Caso 2

Caso 3

Input

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

Atteso

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