Alien Dictionary

+10

Eine Liste von Wörtern ist in einem Alphabet sortiert, das du nicht kennst: den 26 englischen Kleinbuchstaben in einer geheimen Reihenfolge. Wörter werden wie üblich verglichen. Die erste Stelle, an der sich zwei Wörter unterscheiden, entscheidet, und wenn ein Wort der Anfang des anderen ist, kommt das kürzere Wort zuerst.

Gib die Buchstaben, die in den Wörtern vorkommen, als eine Zeichenfolge in alphabetischer Reihenfolge zurück. Wenn mehrere Reihenfolgen passen, gib diejenige zurück, die in der gewöhnlichen Wörterbuchreihenfolge zuerst kommt. Wenn keine Reihenfolge passt, gib "invalid" zurück.

Funktion

alienOrder(words: string-array) → string

wordsstring-array: die Wörter, sortiert nach dem unbekannten Alphabet
Gibt zurückstring: die Buchstaben in der kleinsten passenden Reihenfolge oder „ungültig“

Einschränkungen

1 ≤ words.length ≤ 5000
1 ≤ words[i].length ≤ 10
Jedes Wort enthält ausschließlich englische Kleinbuchstaben.
Dasselbe Wort kann mehr als einmal vorkommen.

Beispiele

Eingabe: words = ["tea", "ten", "ate", "act", "cat"]
Ausgabe: "etacn"
Erklärung: tea vor ten setzt ein a vor ein n. Die anderen Paare ergeben t vor a, t vor c und a vor c. Keine Regel erwähnt e, also beginnt die kleinste Reihenfolge damit: e, t, a, c, n.

Eingabe: words = ["bat", "tab", "tub", "bus"]
Ausgabe: "invalid"
Erklärung: bat vor tab setzt b vor t, und tub vor bus setzt t vor b. Beides kann nicht gelten, also passt keine Reihenfolge.

Eingabe: words = ["cooking", "cook"]
Ausgabe: "invalid"
Erklärung: cook ist der Anfang von cooking, also kommt es in jedem Alphabet zuerst. In der Liste steht es an zweiter Stelle, was sich durch keine Reihenfolge der Buchstaben erklären lässt.

Weiterführende Frage

Wie würdest du feststellen, ob die Reihenfolge der Anpassung die einzige ist?

Tipps

Öffne sie nacheinander. Jeder verrät ein bisschen mehr.

0 von 3 geöffnet

Lösung

Jedes benachbarte Wortpaar ergibt höchstens eine Regel, und zwar an der ersten Stelle, an der sich die Wörter unterscheiden: Buchstabe x vor Buchstabe y. Eine passende Reihenfolge ist eine topologische Sortierung dieser Regeln. Ein Zyklus oder ein Wort, das vor seinem eigenen Präfix steht, macht die Liste unmöglich. Ein Min-Heap, der stets den kleinsten verfügbaren Buchstaben auswählt, liefert die kleinste Reihenfolge.

Probiere jede Reihenfolge der Buchstaben aus

Korrekt, wird aber bei den größten Tests nicht fertig

Idee

Teste eine Anordnung der k verschiedenen Buchstaben, indem du jedes benachbarte Wortpaar überprüfst. An der ersten unterschiedlichen Position muss der Buchstabe des ersten Wortes früher kommen; gibt es keinen Unterschied, darf das erste Wort nicht länger sein. Durchlaufe die Anordnungen ausgehend von der alphabetischen mit der nächsten Permutation aufsteigend. Die erste, die die Bedingungen erfüllt, ist die kleinste passende Anordnung.

k Buchstaben haben k! Anordnungen: 10 ergeben 3,628,800 und 26 etwa 4 × 10^26. Bei jeder Prüfung werden bis zu 5 × 10^4 Zeichen gelesen. Wenn keine Anordnung passt, wird jede einzelne ausprobiert.

Algorithmus

Sammle die unterschiedlichen Buchstaben und sortiere sie alphabetisch.
Notiere den Rang jedes Buchstabens in der aktuellen Anordnung.
Prüfe jedes benachbarte Paar: An der ersten unterschiedlichen Stelle muss der Buchstabe des ersten Wortes einen kleineren Rang haben; gibt es keinen Unterschied, darf das erste Wort nicht länger sein.
Wenn jedes Paar besteht, gib die Anordnung zurück; andernfalls fahre mit der nächstgrößeren fort.
Wenn es keine nächste Anordnung gibt, gib "invalid" zurück.

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"

Kahns Algorithmus mit einem Min-Heap

Idee

Bei einem Paar benachbarter Wörter zählt nur der erste Unterschied: act vor cat bedeutet, dass a vor c kommt, und die Buchstaben danach werden nie verglichen. Jedes Paar liefert also höchstens eine Kante.

Kahns Algorithmus wandelt die Kanten in eine Reihenfolge um: Zähle die eingehenden Kanten jedes Buchstabens, füge einen Buchstaben mit Zählerstand 0 ein, entferne seine ausgehenden Kanten und wiederhole den Vorgang. Ein Buchstabe auf einem Zyklus behält immer eine Kante von dem Buchstaben vor ihm auf dem Zyklus und wird daher nie eingefügt. Wenn weniger Buchstaben eingefügt werden, als vorkommen, lautet die Antwort "invalid".

Halte die verfügbaren Buchstaben in einem Min-Heap und füge jeweils den kleinsten ein. Jede passende Reihenfolge beginnt mit einem verfügbaren Buchstaben, also ist dies der kleinstmögliche erste Buchstabe. Da das Einfügen nur Kanten entfernt, blockiert es keinen anderen Buchstaben. Im ersten Beispiel sind e und t zu Beginn verfügbar, und e kommt zuerst. Eine einfache Warteschlange liefert eine gültige Reihenfolge, aber nicht immer die kleinste.

Algorithmus

Markiere jeden Buchstaben, der in den Wörtern vorkommt.
Suche für jedes benachbarte Wortpaar die erste unterschiedliche Position und füge die Kante zwischen den beiden Buchstaben einmal hinzu. Gibt es keinen Unterschied und ist das erste Wort länger, gib "invalid" zurück.
Zähle die eingehenden Kanten und füge jeden markierten Buchstaben mit Zählerstand 0 in einen Min-Heap ein.
Entnimm den kleinsten Buchstaben und hänge ihn an. Verringere den Zähler jedes Buchstabens, auf den er zeigt, und füge jeden Buchstaben ein, dessen Zählerstand 0 erreicht.
Gib die angeordneten Buchstaben zurück, wenn alle markierten Buchstaben angeordnet wurden, andernfalls "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)

Stolperfallen und Grenzfälle

Mehr als eine Regel aus einem Paar ableiten. Die zweite Position von act und cat zu lesen, fügt c vor a hinzu, und das erste Beispiel wird zu einem falschen Zyklus.
Die Präfix-Falle übersehen. Bei cooking vor cook gibt es keinen unterschiedlichen Buchstaben, sodass eine Schleife, die nur Unterschiede behandelt, eine Reihenfolge zurückgibt.
Buchstaben auslassen, die in keiner Regel vorkommen. Im ersten Beispiel wird e in keiner Regel erwähnt, gehört aber trotzdem zur Antwort.
Eine wiederholte Regel im Eingangsgrad doppelt zählen, aber nur einmal speichern. Der Buchstabe erreicht nie 0, und eine gültige Liste wird als Zyklus gemeldet.
Zwei gleiche benachbarte Wörter als Präfix-Falle behandeln; ein wiederholtes Wort ist in der richtigen Reihenfolge.

Häufige Fragen3

Wie hoch ist die Zeitkomplexität des Alien Dictionary?

O(C + k²), wobei C die Gesamtzahl der Zeichen und k ≤ 26 die Anzahl der unterschiedlichen Buchstaben ist. Ein Durchlauf über die Liste findet jede erste Abweichung, und Kahn's Algorithmus besucht höchstens k² Kanten. Die Kantentabelle benötigt O(k²) Speicherplatz.

Warum nur benachbarte Wörter vergleichen?

Sortiertheit ist transitiv: Wenn jedes Wort höchstens so groß wie das nächste ist, ist die gesamte Liste sortiert. Daher ergibt sich jede Regel, die man aus zwei weit voneinander entfernten Wörtern ablesen könnte, bereits aus den benachbarten Paaren dazwischen.

Warum ist ein Wort vor seinem eigenen Präfix ungültig?

In jedem Alphabet kommt ein Wort nach seinem eigenen Präfix, weil beim Vergleich dem kürzeren Wort die Buchstaben ausgehen, bevor ein Unterschied gefunden wird. Das ist die einzige Möglichkeit, wie eine Liste unmöglich sein kann, ohne dass es einen Zyklus unter ihren Regeln gibt.

def alienOrder(words):
    # Schreibe hier den Code

Test #1

Test #2

Test #3

Argument

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

Erwartete Ausgabe

"etacn"