Alien Dictionary

+10

Un elenco di parole è ordinato secondo un alfabeto che non conosci: le 26 lettere minuscole inglesi in un ordine segreto. Le parole si confrontano nel modo consueto. La prima posizione in cui due parole differiscono determina quale delle due lettere viene prima nell’alfabeto; quando una parola è l’inizio dell’altra, viene prima quella più corta.

Restituisci le lettere che compaiono nelle parole, come un’unica stringa nell’ordine dell’alfabeto. Se più ordini sono compatibili con l’elenco, restituisci quello che viene prima nel normale ordine lessicografico. Se nessun ordine è compatibile, restituisci "invalid".

Funzione

alienOrder(words: string-array) → string

wordsstring-array: le parole, ordinate nell'alfabeto sconosciuto
Restituiscestring: le lettere nell'ordine più piccolo che si adatta, oppure "invalid"

Vincoli

1 ≤ words.length ≤ 5000
1 ≤ words[i].length ≤ 10
Ogni parola contiene solo lettere minuscole inglesi.
La stessa parola può comparire più di una volta.

Esempi

Input: words = ["tea", "ten", "ate", "act", "cat"]
Output: "etacn"
Spiegazione: tea e ten differiscono per la prima volta in a e n, quindi a viene prima di n. Le altre coppie danno t prima di a, t prima di c e a prima di c. Nessuna regola menziona e, quindi l’ordine più piccolo la mette per prima, poi t, poi a, quindi c e n, che a quel punto sono entrambe libere, con c per prima.

Input: words = ["bat", "tab", "tub", "bus"]
Output: "invalid"
Spiegazione: bat prima di tab mette b prima di t, tab prima di tub mette a prima di u e tub prima di bus mette t prima di b. b prima di t e t prima di b non possono valere entrambe, quindi nessun ordine è compatibile.

Input: words = ["cooking", "cook"]
Output: "invalid"
Spiegazione: cook è l'inizio di cooking, quindi viene prima in ogni alfabeto. L'elenco lo mette al secondo posto, cosa che nessun ordine delle lettere può spiegare.

+20 test nascosti all’invio

Per approfondire

Come faresti a capire se l’ordine di adattamento è l’unico?

Suggerimenti

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

0 di 3 aperti

Soluzione

La lista nasconde il suo alfabeto nei punti in cui le parole adiacenti differiscono per la prima volta. Ciascuno di questi punti fornisce una regola, la lettera x prima della lettera y, e le regole formano un grafo diretto sulle lettere. Un ordine valido è un ordinamento topologico di quel grafo. Ci sono due cose che rendono impossibile la lista: un ciclo tra le regole e una parola posizionata prima del proprio prefisso. Posizionare la lettera disponibile più piccola a ogni passaggio, usando un min-heap, produce il più piccolo ordine valido.

Prova tutti gli ordini delle lettere

Corretto, ma non termina sui test più grandi

Intuizione

La risposta è una qualche disposizione delle k lettere distinte. Puoi verificare direttamente una disposizione: l’elenco è compatibile con essa se ogni coppia di parole vicine è in ordine secondo tale disposizione. Confronta le due parole nella prima posizione in cui differiscono: la lettera della prima parola deve comparire prima nella disposizione. Se non differiscono mai, la prima parola non deve essere più lunga. È sufficiente controllare le parole vicine, perché essere ordinate è una catena: se ogni parola è al massimo uguale alla successiva, l’intero elenco è ordinato.

Ora percorri le disposizioni dalla più piccola alla più grande. Inizia con le lettere in ordine alfabetico, che è la disposizione più piccola in assoluto, e passa ogni volta a quella successiva più grande (la permutazione successiva). La prima disposizione che supera la verifica è l’ordine più piccolo compatibile. Se nessuna la supera, restituisci "invalid".

È corretto, ma impraticabile con input reali. k lettere hanno k! disposizioni: 5 lettere ne danno 120, 10 ne danno 3,628,800 e tutte e 26 ne danno circa 4 × 10^26. Ogni verifica legge l’intero elenco, per un totale di C caratteri e fino a 5 × 10^4. Nei test più grandi, il più piccolo ordine compatibile inizia con f o z, quindi prima di raggiungerlo ci sono un numero astronomico di disposizioni; quando non ne è compatibile nessuna, la ricerca deve provarle tutte.

Algoritmo

Raccogli le lettere distinte e ordinalle alfabeticamente.
Registra la posizione di ogni lettera (il suo rango) nella disposizione corrente.
Controlla ogni coppia adiacente: alla prima posizione in cui differiscono, la lettera della prima parola deve avere il rango più piccolo; se non c'è alcuna posizione diversa, la prima parola non deve essere più lunga.
Se tutte le coppie superano il controllo, restituisci la disposizione. Altrimenti passa alla disposizione successiva, più grande.
Quando non c'è una disposizione successiva, restituisci "invalid".

from itertools import permutations


def fits(words, rank):
    # The list is sorted under rank when every neighbouring pair is in order.
    for first, second in zip(words, words[1:]):
        for x, y in zip(first, second):
            if x != y:
                if rank[x] > rank[y]:
                    return False
                break
        else:
            # One word starts the other: the shorter must come first.
            if len(first) > len(second):
                return False
    return True


def alienOrder(words):
    letters = sorted(set("".join(words)))
    # permutations() of a sorted list yields the orders from smallest to largest,
    # so the first order that fits is the answer.
    for order in permutations(letters):
        rank = {ch: i for i, ch in enumerate(order)}
        if fits(words, rank):
            return "".join(order)
    return "invalid"

Algoritmo di Kahn con un min-heap

Intuizione

Ricava le regole dall’elenco invece di indovinare l’ordine. Prendi due parole adiacenti e trova la prima posizione in cui differiscono. tea e ten coincidono per t ed e e differiscono per a e n, quindi a viene prima di n. Questo è tutto il messaggio della coppia. Le lettere dopo la prima differenza non dicono nulla: act viene prima di cat perché a viene prima di c, e la c e la t che seguono in act non vengono mai confrontate con la a e la t di cat. Quindi ogni coppia dà al massimo una regola, un arco da una lettera a un’altra.

Una coppia senza posizioni diverse è la trappola del prefisso. Una parola è l’inizio dell’altra e, in qualsiasi alfabeto, quella più corta deve venire prima. cook prima di cooking va bene e non dà alcuna regola. cooking prima di cook non può mai essere ordinato, quindi restituisci subito "invalid". Un ciclo che cerca soltanto lettere diverse non trova nulla in questa coppia e prosegue restituendo un ordine per un elenco che nessun alfabeto può produrre.

Ora ti serve un ordine delle lettere che rispetti ogni arco, cioè un ordinamento topologico. L’algoritmo di Kahn ne costruisce uno. Conta gli archi diretti verso ogni lettera (il suo grado entrante), inserisci una lettera il cui conteggio è 0, rimuovi i suoi archi uscenti e ripeti. Una lettera che fa parte di un ciclo mantiene sempre un arco proveniente dalla lettera che la precede nel ciclo, quindi il suo conteggio non raggiunge mai 0 e non viene mai inserita. Se vengono inserite meno lettere di quelle presenti nelle parole, c’è un ciclo e la risposta è "invalid".

Per ottenere l’ordine più piccolo, mantieni le lettere con conteggio 0 in un heap min e inserisci sempre la più piccola. Questa scelta greedy è sicura. La prima lettera di qualsiasi ordine valido ha conteggio 0, quindi la lettera pronta più piccola è la prima lettera possibile più piccola. Inserirla rimuove gli archi e non blocca mai un’altra lettera: ogni lettera che era pronta rimane pronta. Lo stesso ragionamento si applica poi alla seconda posizione e così via. Nel primo esempio, all’inizio e e t sono entrambe pronte e viene inserita prima e. Anche una coda semplice produrrebbe un ordine valido, ma non sempre il più piccolo.

Il costo è una scansione dell’elenco, con C caratteri in tutto, per trovare le prime differenze. Con k ≤ 26 lettere, ci sono al massimo k² archi, conservati in una tabella k per k, così una regola ripetuta viene memorizzata una sola volta, e l’heap non contiene mai più di k lettere. Il tempo è quindi O(C + k²), pochi millisecondi anche con i test più grandi.

Algoritmo

Segna ogni lettera che appare nelle parole.
Per ogni coppia di parole adiacenti, trova la prima posizione in cui differiscono. Se esiste, aggiungi una volta l’arco dalla lettera della prima parola alla lettera della seconda. Se non esiste e la prima parola è più lunga, restituisci "invalid".
Conta gli archi entranti di ogni lettera e inserisci in un min-heap ogni lettera che appare e ha conteggio 0.
Estrai la lettera più piccola e aggiungila. Riduci il conteggio di ogni lettera a cui punta e inserisci quelle il cui conteggio raggiunge 0.
Se sono state posizionate meno lettere di quelle presenti, restituisci "invalid". Altrimenti restituisci le lettere posizionate.

import heapq


def alienOrder(words):
    # Letters are numbered 0 for 'a' up to 25 for 'z'.
    present = [False] * 26
    for word in words:
        for ch in word:
            present[ord(ch) - 97] = True
    # before[a][b] is True once you know letter a comes before letter b.
    before = [[False] * 26 for _ in range(26)]
    indegree = [0] * 26
    for first, second in zip(words, words[1:]):
        for x, y in zip(first, second):
            if x != y:
                # Only the first difference tells you anything.
                a, b = ord(x) - 97, ord(y) - 97
                if not before[a][b]:
                    before[a][b] = True
                    indegree[b] += 1
                break
        else:
            # No difference: one word starts the other, so the shorter must come first.
            if len(first) > len(second):
                return "invalid"
    # A min-heap of the letters with nothing left before them.
    heap = [c for c in range(26) if present[c] and indegree[c] == 0]
    heapq.heapify(heap)
    order = []
    while heap:
        c = heapq.heappop(heap)
        order.append(chr(c + 97))
        for nxt in range(26):
            if before[c][nxt]:
                indegree[nxt] -= 1
                if indegree[nxt] == 0:
                    heapq.heappush(heap, nxt)
    # A letter on a cycle never gets down to indegree 0, so it is never placed.
    if len(order) < sum(present):
        return "invalid"
    return "".join(order)

Trappole e casi limite

La maggior parte delle risposte sbagliate qui non dà segnali: una regola interpretata male produce comunque un ordine, solo quello sbagliato.

Considerare più di una regola di una coppia. Conta solo la prima posizione diversa. act prima di cat indica che a viene prima di c e non dice nulla sulle lettere successive.
Non accorgersi della trappola del prefisso. cooking prima di cook non presenta lettere diverse, quindi un ciclo che gestisce solo le differenze non rileva nulla e restituisce un ordine. La risposta è "invalid".
Omettere le lettere che non compaiono in nessuna regola. Nel primo esempio nessuna regola menziona e, eppure deve comparire nella risposta, e l'ordine più piccolo la mette per prima.
Usare una coda semplice invece di un min-heap. L'algoritmo di Kahn con una coda restituisce un ordine valido, ma il contratto richiede quello più piccolo.
Contare una regola ripetuta due volte nel grado entrante, ma memorizzarla una sola volta nel grafo. La lettera non raggiunge mai 0 e una lista valida viene segnalata come ciclo. Memorizza ogni regola una sola volta, oppure aggiungila e rimuovila lo stesso numero di volte.
Considerare due parole uguali adiacenti come una trappola del prefisso. Una parola seguita dalla stessa parola è in ordine; solo una parola più lunga che precede il proprio prefisso è impossibile.

Domande frequenti4

Qual è la complessità temporale di Alien Dictionary?

O(C + k²), dove C è il numero totale di caratteri nelle parole e k ≤ 26 è il numero di lettere distinte. Un passaggio sull’elenco individua la prima differenza di ogni coppia di parole vicine e l’algoritmo di Kahn visita al massimo k² archi. Il min-heap aggiunge O(k log k), una quantità ridotta rispetto al resto. La tabella degli archi occupa O(k²) spazio.

Perché confrontare solo le parole vicine?

Essere ordinata è una proprietà transitiva: se ogni parola è minore o uguale alla successiva, l'intera lista è ordinata. Quindi, qualsiasi regola tu possa dedurre da due parole distanti è già implicata dalle coppie adiacenti che si trovano tra loro. Confrontare ogni coppia di parole non aggiunge informazioni e richiede O(n²) confronti invece di n-1.

Perché scegliere la lettera pronta più piccola dà l’ordine più piccolo?

Qualsiasi ordinamento valido deve iniziare con una lettera a cui non punta nessuna regola. La lettera più piccola di questo tipo è quindi la più piccola possibile come prima lettera e, posizionandola, si rimuovono solo archi, quindi tutte le altre lettere pronte restano disponibili. Ripetendo il ragionamento per ogni posizione, si costruisce l’ordinamento più piccolo lettera per lettera. Un min-heap ti restituisce la lettera pronta più piccola in O(log k).

Perché una parola prima del proprio prefisso non è valida?

In ogni alfabeto una parola viene dopo il proprio prefisso, perché il confronto esaurisce le lettere della parola più corta prima di trovare una differenza. Quindi cooking prima di cook è fuori ordine, qualunque siano le lettere, e nessuna regola può correggerlo. È l’unico modo in cui una lista può essere impossibile senza che ci sia alcun ciclo tra le sue regole.

Python

def alienOrder(words):
    # Scrivi il codice qui

Casi di test

Caso 1

Caso 2

Caso 3

Input

words = ["tea", "ten", "ate", "act", "cat"]

Atteso

"etacn"