Group Anagrams

Q: Qual è la complessità temporale di Group Anagrams?

La creazione delle chiavi con le lettere ordinate richiede O(n · k log k) per n parole composte da un massimo di k lettere, mentre il lavoro sulla mappa richiede O(n · k) . Ordinare le parole per ordinare l’output aggiunge O(n · k · log n) , che è il termine dominante. Lo spazio richiesto è O(n · k) per le chiavi e i gruppi.

MedioHashing Ordinamento

+10

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

Una parola ripetuta è elencata due volte nel suo gruppo e una parola senza anagrammi forma un gruppo di una sola parola. Per ordine alfabetico si intende l’ordine da 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 dell’alfabeto inglese.

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 una volta ciascuna le lettere e, i, l, n, s e t. notes, onset, stone e tones hanno in comune e, n, o, s e t. apple non corrisponde a nulla e, essendo la prima parola, è in testa.

Input: strs = ["race", "arc", "care", "car", "acre"]
Output: ["acre care race", "arc car"]
Spiegazione: acre, care e race condividono a, c, e e r. arc e car non hanno la e, quindi formano un gruppo a sé. acre viene prima di arc perché la c precede la 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 corrispondente e viene prima.

Per approfondire

Se le parole potessero contenere qualsiasi carattere Unicode, quale chiave, lettere ordinate o conteggi delle lettere, funzionerebbe comunque e cosa cambieresti?

Suggerimenti

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

0 di 3 aperti

Soluzione

Calcola una chiave da ogni parola, considerata da sola, che sia uguale per tutti i suoi anagrammi e diversa per ogni altra parola. Le lettere di una parola in ordine alfabetico costituiscono una chiave del genere, e una mappa hash dalla chiave al gruppo raccoglie i gruppi in un solo passaggio. Ordina prima le parole e l’ordine richiesto si ottiene automaticamente.

Confronta ogni parola con ogni gruppo

Corretto, ma non termina sui test più grandi

Intuizione

Mantieni un elenco di gruppi e confronta ogni parola con la prima parola di ciascun gruppo. Essere anagrammi è una relazione transitiva, quindi basta un confronto per gruppo per decidere l'appartenenza. Due parole sono anagrammi quando hanno la stessa lunghezza e lo stesso conteggio per ciascuna delle 26 lettere. Ordina prima l'input: ogni gruppo si completa quindi in ordine alfabetico e i gruppi vengono creati nell'ordine della loro prima parola.

Quando non ci sono due parole che sono anagrammi, ogni parola viene confrontata con tutti i gruppi che la precedono: 4000 parole comportano circa 8 × 10^6 confronti, ciascuno dei quali riguarda fino a 8 lettere e 26 contatori.

Algoritmo

Ordina le parole in ordine alfabetico.
Per ogni parola, trova un gruppo la cui prima parola abbia lo stesso conteggio di lettere e aggiungi la parola. Se nessun gruppo corrisponde, creane uno nuovo.
Restituisci le parole di ogni gruppo unite da spazi singoli, nell'ordine di creazione.

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

Calcola il nome del gruppo a partire dalla parola stessa. Ordina le lettere di una parola e ogni anagramma restituisce lo stesso testo: listen, silent e enlist diventano tutti eilnst, mentre stone diventa enost. Due parole condividono una forma ordinata esattamente quando contengono le stesse lettere lo stesso numero di volte, che è la definizione di anagramma. Una mappa hash che associa ogni chiave a un elenco di parole raggruppa tutto in un solo passaggio, senza confrontare alcuna parola con un altro gruppo.

L'ordine deriva dall'ordinamento preliminare dell'input, come prima: ogni elenco si riempie in ordine alfabetico e una chiave entra nella mappa quando arriva la prima parola del suo gruppo. Una mappa che mantiene l'ordine di inserimento restituisce i gruppi in quell'ordine; altrimenti, conserva i gruppi in un elenco e associa ogni chiave al relativo indice.

L'ordinamento dell'input richiede circa 5 × 10^4 confronti tra parole per 4000 parole, invece di 8 × 10^6.

Algoritmo

Ordina le parole in ordine alfabetico.
Per ogni parola, crea la sua chiave ordinando le lettere.
Cerca la chiave in una mappa hash. Se è nuova, crea un gruppo vuoto per essa, mantenendo i gruppi nell'ordine in cui li crei.
Aggiungi la parola al gruppo corrispondente alla sua chiave.
Restituisci le parole di ciascun gruppo unite da singoli spazi, 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

Ordinare i gruppi in base alla chiave invece che alla prima parola. Per ["cab", "bad"] le chiavi abc e abd mettono cab per primo, ma bad dovrebbe essere in testa.
Raccogliere le parole in un insieme. ["b", "a", "b"] deve restituire b b; un insieme conserva una sola copia.
Creare una chiave usando solo le lettere distinte. ab e aabb usano le stesse due lettere, ma non sono anagrammi.
Ordinare ogni gruppo, ma non l'input e nemmeno i gruppi. L'ordine di inserimento segue quindi l'input, non le prime parole.

Domande frequenti3

Qual è la complessità temporale di Group Anagrams?

La creazione delle chiavi con le lettere ordinate richiede O(n · k log k) per n parole composte da un massimo di k lettere, mentre il lavoro sulla mappa richiede O(n · k). Ordinare le parole per ordinare l’output aggiunge O(n · k · log n), che è il termine dominante. Lo spazio richiesto è O(n · k) per le chiavi e i gruppi.

Una chiave basata sul conteggio delle lettere è più veloce dell'ordinamento di ogni parola?

Una chiave di conteggio, i conteggi delle 26 lettere scritti come testo, ad esempio 1#0#2#…, richiede O(k) invece di O(k log k), quindi è più efficiente con le parole lunghe. Con 8 lettere o meno, l’ordinamento è altrettanto veloce. Entrambe le chiavi sono esatte: due parole hanno gli stessi conteggi se e solo se 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 condividerebbero un gruppo. Il prodotto di un numero primo per lettera è preciso, ma con 101 per z, una parola composta da dieci z supera i limiti di un intero a 64 bit.

def groupAnagrams(strs):
    # Scrivi il codice qui

Test #1

Test #2

Test #3

Argomento

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

Output atteso

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