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 auf die übliche Weise verglichen. Die erste Stelle, an der sich zwei Wörter unterscheiden, entscheidet darüber, welcher der beiden Buchstaben im Alphabet zuerst kommt. Ist ein Wort der Anfang des anderen, 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 zur Liste 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 „invalid“

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 und ten unterscheiden sich zuerst bei a und n, also kommt a vor n. Die anderen Paare ergeben t vor a, t vor c und a vor c. Keine Regel erwähnt e, daher setzt die kleinste Reihenfolge e an den Anfang, dann t, dann a, dann c und n, die beide zu diesem Zeitpunkt frei sind, wobei c zuerst kommt.

Eingabe: words = ["bat", "tab", "tub", "bus"]
Ausgabe: "invalid"
Erklärung: bat vor tab setzt b vor t, tab vor tub setzt a vor u, und tub vor bus setzt t vor b. b vor t und t vor b können nicht gleichzeitig gelten, daher passt keine Reihenfolge.

Eingabe: words = ["cooking", "cook"]
Ausgabe: "invalid"
Erklärung: cook ist der Anfang von cooking, deshalb 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.

+20 versteckte Tests beim Einreichen

Weiterführende Frage

Woran würdest du erkennen, ob die Anpassungsreihenfolge die einzige ist?

Tipps

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

0 von 3 geöffnet

Lösung

Die Liste verbirgt ihr Alphabet an den Stellen, an denen sich benachbarte Wörter zum ersten Mal unterscheiden. Jede solche Stelle ergibt eine Regel: Buchstabe x vor Buchstabe y, und die Regeln bilden einen gerichteten Graphen über den Buchstaben. Eine passende Reihenfolge ist eine topologische Sortierung dieses Graphen. Zwei Dinge machen die Liste unmöglich: ein Zyklus unter den Regeln und ein Wort, das vor seinem eigenen Präfix steht. Wenn man bei jedem Schritt den kleinsten verfügbaren Buchstaben mit einem Min-Heap auswählt, erhält man die kleinste passende Reihenfolge.

Probiere jede Reihenfolge der Buchstaben aus

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

Idee

Die Antwort ist eine Anordnung der k verschiedenen Buchstaben. Du kannst eine Anordnung direkt testen: Die Liste passt dazu, wenn jedes benachbarte Wortpaar gemäß dieser Anordnung sortiert ist. Vergleiche die beiden Wörter an der ersten Position, an der sie sich unterscheiden; der Buchstabe des ersten Wortes muss in der Anordnung früher kommen. Wenn sie sich nie unterscheiden, darf das erste Wort nicht länger sein. Benachbarte Wörter reichen aus, denn sortiert zu sein ist transitiv: Wenn jedes Wort höchstens so groß wie das nächste ist, ist die gesamte Liste sortiert.

Gehe nun die Anordnungen von der kleinsten zur größten durch. Beginne mit den Buchstaben in alphabetischer Reihenfolge, also mit der kleinsten Anordnung überhaupt, und gehe jedes Mal zum nächstgrößeren über (zur nächsten Permutation). Die erste Anordnung, die den Test besteht, ist die kleinste passende Reihenfolge. Wenn keine den Test besteht, gib "invalid" zurück.

Das ist korrekt, aber bei echten Eingaben aussichtslos. k Buchstaben haben k! Anordnungen: 5 Buchstaben ergeben 120, 10 ergeben 3,628,800, und alle 26 ergeben etwa 4 × 10^26. Jeder Test liest die gesamte Liste, insgesamt C Zeichen und bis zu 5 × 10^4. Bei den großen Tests beginnt die kleinste passende Reihenfolge mit f oder z, sodass ihr eine astronomische Anzahl von Anordnungen vorausgeht. Und wenn keine Anordnung passt, muss die Suche jede einzelne ausprobieren.

Algorithmus

Ermittle die unterschiedlichen Buchstaben und sortiere sie alphabetisch.
Erfasse die Position jedes Buchstabens (seinen Rang) in der aktuellen Anordnung.
Prüfe jedes benachbarte Paar: An der ersten unterschiedlichen Position muss der Buchstabe des ersten Wortes den kleineren Rang haben; gibt es keine unterschiedliche Position, darf das erste Wort nicht länger sein.
Wenn jedes Paar die Prüfung besteht, gib die Anordnung zurück. Andernfalls gehe zur nächstgrößeren Anordnung über.
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

Lies die Regeln aus der Liste ab, statt die Reihenfolge zu erraten. Nimm zwei benachbarte Wörter und finde die erste Position, an der sie sich unterscheiden. tea und ten stimmen bei t und e überein und unterscheiden sich bei a und n, also kommt a vor n. Das ist die gesamte Aussage des Paars. Die Buchstaben nach dem ersten Unterschied sagen nichts aus: act kommt vor cat, weil a vor c kommt, und das c und t, die in act folgen, werden niemals mit dem a und t von cat verglichen. Jedes Paar liefert also höchstens eine Regel, eine Kante von einem Buchstaben zu einem anderen.

Ein Paar ohne abweichende Position ist die Präfix-Falle. Ein Wort ist der Anfang des anderen, und das kürzere muss in jedem Alphabet zuerst kommen. cook vor cooking ist in Ordnung und liefert keine Regel. cooking vor cook lässt sich niemals sortieren, also gib sofort "invalid" zurück. Eine Schleife, die nur nach unterschiedlichen Buchstaben sucht, findet in diesem Paar nichts und gibt anschließend eine Reihenfolge für eine Liste zurück, die kein Alphabet hervorbringen kann.

Nun brauchst du eine Reihenfolge der Buchstaben, die alle Kanten berücksichtigt: eine topologische Ordnung. Kahn's Algorithmus erstellt eine solche. Zähle die Kanten, die auf jeden Buchstaben zeigen (seinen Eingangsgrad), nimm einen Buchstaben mit einem Zähler von 0, 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, daher erreicht sein Zähler niemals 0 und er wird nie aufgenommen. Wenn weniger Buchstaben aufgenommen werden, als in den Wörtern vorkommen, gibt es einen Zyklus und die Antwort ist "invalid".

Um die kleinste Reihenfolge zu erhalten, halte die Buchstaben mit einem Zähler von 0 in einem Min-Heap und nimm immer den kleinsten auf. Diese gierige Wahl ist sicher. Der erste Buchstabe jeder passenden Reihenfolge hat den Eingangsgrad 0, daher ist der kleinste verfügbare Buchstabe der kleinstmögliche erste Buchstabe. Ihn aufzunehmen entfernt Kanten und blockiert niemals einen anderen Buchstaben: Jeder Buchstabe, der bereits verfügbar war, bleibt verfügbar. Dasselbe Argument gilt dann für die zweite Position und so weiter. Im ersten Beispiel sind e und t zu Beginn beide verfügbar, und e kommt zuerst. Eine normale Warteschlange würde ebenfalls eine gültige Reihenfolge liefern, aber nicht immer die kleinste.

Der Aufwand besteht aus einem Durchlauf über die Liste mit insgesamt C Zeichen, um die ersten Unterschiede zu finden. Bei k ≤ 26 Buchstaben gibt es höchstens k² Kanten, die in einer k-mal-k-Tabelle gespeichert werden, sodass eine wiederholte Regel nur einmal gespeichert wird, und der Heap enthält nie mehr als k Buchstaben. Das ergibt O(C + k²) Zeit, also einige Millisekunden bei den größten Tests.

Algorithmus

Markiere jeden Buchstaben, der in den Wörtern vorkommt.
Finde für jedes benachbarte Wortpaar die erste unterschiedliche Position. Gibt es eine, füge einmal die Kante vom Buchstaben des ersten Wortes zum Buchstaben des zweiten Wortes hinzu. Gibt es keine und ist das erste Wort länger, gib "invalid" zurück.
Zähle für jeden Buchstaben die eingehenden Kanten und füge jeden vorkommenden Buchstaben mit Anzahl 0 zu einem Min-Heap hinzu.
Entnimm den kleinsten Buchstaben und hänge ihn an. Verringere die Anzahl jedes Buchstabens, auf den er zeigt, und füge jeden hinzu, dessen Anzahl 0 erreicht.
Wenn weniger Buchstaben platziert wurden, als vorkommen, gib "invalid" zurück. Andernfalls gib die platzierten Buchstaben zurück.

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

Die meisten falschen Antworten hier bleiben unbemerkt: Eine falsch gelesene Regel erzeugt trotzdem irgendeine Reihenfolge, nur eben die falsche.

Mehr als eine Regel aus einem Wortpaar übernehmen. Es zählt nur die erste unterschiedliche Position. act vor cat sagt aus, dass a vor c kommt, und nichts über die darauffolgenden Buchstaben.
Die Präfix-Falle übersehen. Bei cooking vor cook gibt es keinen unterschiedlichen Buchstaben, daher erkennt eine Schleife, die nur Unterschiede behandelt, nichts und gibt eine Reihenfolge zurück. Die Antwort lautet "invalid".
Buchstaben weglassen, die in keiner Regel vorkommen. Im ersten Beispiel erwähnt keine Regel e, dennoch gehört es in die Antwort, und die kleinste Reihenfolge setzt es an den Anfang.
Eine einfache Warteschlange statt eines Min-Heaps verwenden. Kahns Algorithmus mit einer Warteschlange gibt eine gültige Reihenfolge zurück, aber laut Spezifikation ist die kleinste gefragt.
Eine wiederholte Regel beim Eingangsgrad doppelt zählen, sie aber nur einmal im Graphen speichern. Der Buchstabe erreicht dann nie 0, und eine gültige Liste wird als Zyklus gemeldet. Speichere jede Regel nur einmal oder füge sie hinzu und entferne sie gleich oft.
Zwei gleiche benachbarte Wörter als Präfix-Falle behandeln. Auf ein Wort darf dasselbe Wort folgen; unmöglich ist nur ein längeres Wort vor seinem eigenen Präfix.

Häufige Fragen4

Wie hoch ist die Zeitkomplexität des Alien Dictionary?

O(C + k²), wobei C die Gesamtzahl der Zeichen in den Wörtern ist und k ≤ 26 die Anzahl der unterschiedlichen Buchstaben. Ein Durchlauf über die Liste findet den ersten Unterschied jedes benachbarten Paars, und Kahns Algorithmus besucht höchstens k² Kanten. Der Min-Heap benötigt O(k log k), was im Vergleich zum Rest gering ist. 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 ganze Liste sortiert. Daher folgt jede Regel, die sich aus zwei weit voneinander entfernten Wörtern ablesen lässt, bereits aus den benachbarten Paaren dazwischen. Jedes Wortpaar zu vergleichen, liefert keine zusätzlichen Informationen und kostet O(n²) Vergleiche statt n-1.

Warum ergibt die Auswahl des alphabetisch kleinsten verfügbaren Buchstabens die kleinste Reihenfolge?

Jede passende Reihenfolge muss mit einem Buchstaben beginnen, auf den keine Regel verweist. Der kleinste solche Buchstabe ist daher der kleinstmögliche erste Buchstabe, und seine Platzierung entfernt nur Kanten, sodass jeder andere verfügbare Buchstabe weiterhin verfügbar bleibt. Wiederholt man das Argument an jeder Position, entsteht die kleinste Reihenfolge Buchstabe für Buchstabe. Ein Min-Heap liefert dir den kleinsten verfügbaren Buchstaben in O(log k).

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. Daher ist cooking vor cook ungeordnet, unabhängig davon, um welche Buchstaben es sich handelt, und keine Regel kann das korrigieren. Das ist die einzige Möglichkeit, wie eine Liste unmöglich sein kann, ohne dass es einen Zyklus unter ihren Regeln gibt.

Python

def alienOrder(words):
    # Schreibe hier den Code

Testfälle

Fall 1

Fall 2

Fall 3

Eingabe

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

Erwartet

"etacn"