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 come al solito. Decide la prima posizione in cui due parole differiscono e, quando una parola è l'inizio dell'altra, viene prima quella più corta.

Restituisci le lettere presenti nelle parole, come un'unica stringa nell'ordine dell'alfabeto. Quando sono possibili più ordini, restituisci quello che viene prima nel normale ordine alfabetico. Quando nessun ordine è possibile, restituisci "invalid".

Funzione

alienOrder(words: string-array) → string

wordsstring-array: le parole, ordinate secondo l'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 inglesi minuscole.
La stessa parola può comparire più di una volta.

Esempi

Input: words = ["tea", "ten", "ate", "act", "cat"]
Output: "etacn"
Spiegazione: tea prima di ten colloca a prima di n. Le altre coppie indicano t prima di a, t prima di c e a prima di c. Nessuna regola menziona e, quindi l’ordine più piccolo inizia con essa: e, t, a, c, n.

Input: words = ["bat", "tab", "tub", "bus"]
Output: "invalid"
Spiegazione: bat prima di tab mette b prima di t, e tub prima di bus mette t prima di b. Non possono essere vere entrambe le condizioni, quindi nessun ordine è valido.

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.

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

Ogni coppia di parole adiacenti fornisce al massimo una regola, nella prima posizione in cui differiscono: la lettera x prima della lettera y. Un ordine valido è un ordinamento topologico di queste regole. Un ciclo, oppure una parola collocata prima del proprio prefisso, rende impossibile l'elenco. Un min-heap che colloca sempre la lettera disponibile più piccola fornisce l'ordine più piccolo.

Prova ogni ordine delle lettere

Corretto, ma non termina sui test più grandi

Intuizione

Verifica una disposizione delle k lettere distinte controllando ogni coppia di parole vicine. Nella prima posizione in cui differiscono, la lettera della prima parola deve venire prima; se non ci sono differenze, la prima parola non deve essere più lunga. Scorri le disposizioni in ordine crescente a partire da quella alfabetica usando la permutazione successiva: la prima che soddisfa i requisiti è l’ordine minimo compatibile.

Le k lettere hanno k! disposizioni: 10 ne danno 3,628,800 e 26 circa 4 × 10^26, e ogni verifica legge fino a 5 × 10^4 caratteri. Se non c’è nessuna disposizione compatibile, la ricerca le prova tutte.

Algoritmo

Raccogli le lettere distinte e ordinalle alfabeticamente.
Registra il rango di ogni lettera nella disposizione corrente.
Controlla ogni coppia di parole vicine: alla prima posizione diversa, la lettera della prima parola deve avere un rango minore; se non ci sono differenze, la prima parola non deve essere più lunga.
Se ogni coppia supera il controllo, restituisci la disposizione; altrimenti passa a quella successiva più grande.
Quando non esiste 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 heap minimo

Intuizione

In una coppia di parole vicine conta solo la prima differenza: act prima di cat indica che a precede c, e le lettere successive non vengono mai confrontate. Quindi ogni coppia dà al massimo un arco.

L'algoritmo di Kahn trasforma gli archi in un ordinamento: conta gli archi entranti di ogni lettera, inserisce una lettera il cui conteggio è 0, rimuove i suoi archi uscenti e ripete. Una lettera appartenente a un ciclo mantiene sempre un arco proveniente dalla lettera che la precede nel ciclo, quindi non viene mai inserita. Se vengono inserite meno lettere di quelle presenti, la risposta è "invalid".

Mantieni le lettere pronte in un min-heap e inserisci la più piccola. Qualsiasi ordinamento valido inizia con una lettera pronta, quindi questa è la prima lettera più piccola possibile; inoltre, inserirla rimuove solo archi, quindi non blocca nessun'altra lettera. Nel primo esempio, all'inizio sono pronte e e t, e viene inserita prima e. Una coda normale dà un ordinamento valido, ma non sempre il più piccolo.

Algoritmo

Segna ogni lettera presente nelle parole.
Per ogni coppia di parole vicine, trova la prima posizione in cui differiscono e aggiungi una volta l’arco tra le due lettere corrispondenti. Se non ci sono differenze e la prima parola è più lunga, restituisci "invalid".
Conta gli archi entranti e inserisci in un min-heap ogni lettera segnata con conteggio 0.
Estrai la lettera più piccola e aggiungila. Riduci il conteggio di ogni lettera verso cui punta e inserisci quelle che raggiungono 0.
Restituisci le lettere inserite se sono state inserite tutte le lettere segnate; altrimenti, "invalid".

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

Prendere più di una regola da una coppia. Leggere la seconda posizione di act e cat aggiunge c prima di a, e il primo esempio diventa un ciclo falso.
Non considerare la trappola del prefisso. cooking prima di cook non presenta lettere diverse, quindi un ciclo che gestisce solo le differenze restituisce un ordine.
Omettere le lettere che non compaiono in nessuna regola. Nel primo esempio nessuna regola menziona e, eppure deve comparire nella risposta.
Contare due volte una regola ripetuta nel grado entrante, ma memorizzarla una sola volta. La lettera non raggiunge mai 0 e una lista valida viene segnalata come ciclo.
Considerare due parole uguali adiacenti come una trappola del prefisso; una parola ripetuta rispetta l'ordine.

Domande frequenti3

Qual è la complessità temporale di Alien Dictionary?

O(C + k²), dove C è il numero totale di caratteri e k ≤ 26 è il numero di lettere distinte. Una passata sulla lista trova ogni prima differenza e l'algoritmo di Kahn visita al massimo k² archi. La tabella degli archi occupa O(k²) di spazio.

Perché confrontare solo le parole adiacenti?

Essere ordinati è una proprietà transitiva: se ogni parola è al massimo uguale alla successiva, l’intera lista è ordinata. Quindi, qualsiasi regola tu possa dedurre da due parole distanti è già implicata dalle coppie di parole vicine che si trovano tra loro.

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. È l'unico modo in cui una lista può essere impossibile senza che ci sia un ciclo tra le sue regole.

def alienOrder(words):
    # Scrivi il codice qui

Test #1

Test #2

Test #3

Argomento

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

Output atteso

"etacn"