Alien Dictionary

+10

Lista słów jest posortowana w alfabecie, którego nie znasz: 26 małych liter angielskich w pewnej tajnej kolejności. Słowa porównuje się w zwykły sposób. O pierwszeństwie decyduje pierwsza pozycja, na której dwa słowa się różnią: to, która z dwóch liter występuje wcześniej w alfabecie. Jeśli jedno słowo jest początkiem drugiego, pierwsze występuje krótsze słowo.

Zwróć litery występujące w słowach jako jeden ciąg znaków uporządkowany alfabetycznie. Jeśli do listy pasuje kilka kolejności, zwróć tę, która jest pierwsza w zwykłym porządku słownikowym. Jeśli nie pasuje żadna kolejność, zwróć "invalid".

Funkcja

alienOrder(words: string-array) → string

wordsstring-array: słowa, posortowane w nieznanym alfabecie
Zwracastring: litery w najmniejszej pasującej kolejności albo „nieprawidłowe”

Ograniczenia

1 ≤ words.length ≤ 5000
1 ≤ words[i].length ≤ 10
Każde słowo zawiera wyłącznie małe litery angielskiego alfabetu.
To samo słowo może pojawić się więcej niż raz.

Przykłady

Wejście: words = ["tea", "ten", "ate", "act", "cat"]
Wyjście: "etacn"
Wyjaśnienie: tea i ten różnią się po raz pierwszy na literach a i n, więc a występuje przed n. Pozostałe pary wskazują, że t występuje przed a, t przed c, a a przed c. Żadna reguła nie wspomina o e, więc najmniejszy porządek umieszcza je na początku, następnie t, potem a, a na końcu c i n, które do tego momentu nie są już ograniczone żadną regułą, przy czym c występuje jako pierwsze.

Wejście: words = ["bat", "tab", "tub", "bus"]
Wyjście: "invalid"
Wyjaśnienie: bat przed tab umieszcza b przed t, tab przed tub umieszcza a przed u, a tub przed bus umieszcza t przed b. b przed t i t przed b nie mogą zachodzić jednocześnie, więc żaden porządek nie pasuje.

Wejście: words = ["cooking", "cook"]
Wyjście: "invalid"
Wyjaśnienie: cook to początek słowa cooking, więc w każdym alfabecie powinno występować jako pierwsze. Lista umieszcza je na drugim miejscu, czego nie da się wyjaśnić żadnym porządkiem liter.

+20 ukrytych testów przy wysłaniu

Pytanie dodatkowe

Jak sprawdzić, czy kolejność dopasowania jest jedyną możliwą?

Podpowiedzi

Otwieraj je po kolei. Każda zdradza trochę więcej.

Otwarte: 0 z 3

Rozwiązanie

Lista ukrywa swój alfabet w miejscach, w których sąsiadujące ze sobą słowa różnią się po raz pierwszy. Każde takie miejsce określa jedną regułę: litera x przed literą y, a reguły tworzą skierowany graf liter. Pasujący porządek jest porządkiem topologicznym tego grafu. Dwie rzeczy sprawiają, że lista jest niemożliwa: cykl wśród reguł oraz słowo umieszczone przed własnym prefiksem. Umieszczanie na każdym kroku najmniejszej dostępnej litery za pomocą kopca minimum daje najmniejszy pasujący porządek.

Wypróbuj każdą kolejność liter

Poprawne, ale nie kończy się na największych testach

Intuicja

Odpowiedzią jest pewne uporządkowanie k różnych liter. Możesz bezpośrednio sprawdzić jedno uporządkowanie: lista pasuje do niego, jeśli każda para sąsiednich słów jest w nim uporządkowana. Porównaj oba słowa w pierwszym miejscu, w którym się różnią; litera z pierwszego słowa musi występować wcześniej w uporządkowaniu. Jeśli nigdy się nie różnią, pierwsze słowo nie może być dłuższe. Wystarczą sąsiednie słowa, ponieważ sortowanie tworzy łańcuch: jeśli każde słowo jest nie większe od następnego, cała lista jest posortowana.

Teraz przechodź przez uporządkowania od najmniejszego do największego. Zacznij od liter w kolejności alfabetycznej, która jest najmniejszym ze wszystkich uporządkowań, a następnie za każdym razem przejdź do kolejnego większego uporządkowania (następnej permutacji). Pierwsze uporządkowanie, które przejdzie test, jest najmniejszym pasującym porządkiem. Jeśli żadne nie przejdzie, zwróć "invalid".

To rozwiązanie jest poprawne, ale beznadziejne przy rzeczywistych danych wejściowych. k liter ma k! uporządkowań: 5 liter daje 120, 10 daje 3,628,800, a wszystkie 26 dają około 4 × 10^26. Każdy test odczytuje całą listę, łącznie C znaków, maksymalnie 5 × 10^4. W dużych testach najmniejsze pasujące uporządkowanie zaczyna się od f lub z, więc poprzedza je astronomiczna liczba uporządkowań, a gdy żadne nie pasuje, wyszukiwanie musi wypróbować każde z nich.

Algorytm

Zbierz różne litery i posortuj je alfabetycznie.
Zapisz pozycję każdej litery (jej rangę) w bieżącym układzie.
Sprawdź każdą sąsiednią parę: na pierwszej różniącej się pozycji litera z pierwszego słowa musi mieć mniejszą rangę; jeśli nie ma różniącej się pozycji, pierwsze słowo nie może być dłuższe.
Jeśli każda para przejdzie sprawdzenie, zwróć układ. W przeciwnym razie przejdź do następnego większego układu.
Jeśli nie ma następnego układu, zwróć "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"

Algorytm Kahna z kopcem minimalnym

Intuicja

Odczytuj reguły z listy zamiast zgadywać kolejność. Weź dwa sąsiednie słowa i znajdź pierwszą pozycję, na której się różnią. tea i ten są zgodne w przypadku t i e, a różnią się przy a i n, więc a występuje przed n. To cała informacja, jaką niesie ta para. Litery po pierwszej różnicy nic nie mówią: act występuje przed cat, ponieważ a występuje przed c, a c i t, które następują po nim w act, nigdy nie są porównywane z a i t z cat. Każda para daje więc co najwyżej jedną regułę — krawędź od jednej litery do drugiej.

Para bez żadnej różniącej się pozycji to pułapka prefiksu. Jedno słowo jest początkiem drugiego, a krótsze musi występować wcześniej w każdym alfabecie. cook przed cooking jest poprawne i nie daje żadnej reguły. cooking przed cook nigdy nie da się uporządkować, więc od razu zwróć "invalid". Pętla, która szuka tylko różniących się liter, niczego w tej parze nie znajdzie i przejdzie dalej, by zwrócić kolejność dla listy, której żaden alfabet nie może wygenerować.

Teraz potrzebujesz kolejności liter, która spełnia wszystkie krawędzie — porządku topologicznego. Algorytm Kahna tworzy taki porządek. Policz krawędzie skierowane do każdej litery (jej stopień wejściowy), umieść literę, której licznik wynosi 0, usuń jej krawędzie wychodzące i powtarzaj. Litera należąca do cyklu zawsze zachowuje krawędź od poprzedzającej ją litery w cyklu, więc jej licznik nigdy nie spada do 0 i nigdy nie zostaje umieszczona. Jeśli umieszczono mniej liter, niż występuje w słowach, istnieje cykl, a odpowiedzią jest "invalid".

Aby uzyskać najmniejszy porządek, przechowuj litery, których licznik wynosi 0, w kopcu minimalnym i zawsze umieszczaj najmniejszą. Ten zachłanny wybór jest bezpieczny. Pierwsza litera dowolnego pasującego porządku ma stopień wejściowy 0, więc najmniejsza gotowa litera jest najmniejszą możliwą pierwszą literą. Umieszczenie jej usuwa krawędzie i nigdy nie blokuje innej litery: każda litera, która była gotowa, pozostaje gotowa. Ten sam argument stosuje się następnie do drugiej pozycji i tak dalej. W pierwszym przykładzie e i t są gotowe na początku, a e trafia na pierwsze miejsce. Zwykła kolejka również dałaby poprawny porządek, ale nie zawsze najmniejszy.

Wymaga to jednego przejścia po liście, zawierającej łącznie C znaków, aby znaleźć pierwsze różnice. Przy k ≤ 26 literach istnieje najwyżej k² krawędzi, przechowywanych w tabeli k na k, tak aby powtarzającą się regułę zapisać tylko raz, a kopiec nigdy nie zawiera więcej niż k liter. Daje to złożoność czasową O(C + k²) — kilka milisekund przy największych testach.

Algorytm

Oznacz każdą literę występującą w słowach.
Dla każdej pary sąsiadujących słów znajdź pierwszą pozycję, na której się różnią. Jeśli taka pozycja istnieje, dodaj krawędź od litery z pierwszego słowa do litery z drugiego słowa, tylko raz. Jeśli takiej pozycji nie ma, a pierwsze słowo jest dłuższe, zwróć "invalid".
Policz krawędzie wchodzące do każdej litery i umieść każdą występującą literę, której liczba wynosi 0, w kopcu minimalnym.
Usuń najmniejszą literę z kopca i dołącz ją. Zmniejsz liczbę dla każdej litery, na którą wskazuje, i umieść w kopcu każdą literę, której liczba spadnie do 0.
Jeśli umieszczono mniej liter, niż występuje, zwróć "invalid". W przeciwnym razie zwróć umieszczone litery.

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)

Pułapki i przypadki brzegowe

Większość błędnych odpowiedzi w tym zadaniu nie daje żadnych wyraźnych oznak błędu: błędnie odczytana reguła nadal prowadzi do jakiegoś uporządkowania, tylko niewłaściwego.

Uwzględnianie więcej niż jednej reguły z pary. Liczy się tylko pierwsza różniąca się pozycja. act przed cat oznacza, że a jest przed c, i nie mówi nic o kolejnych literach.
Przeoczenie pułapki związanej z prefiksem. cooking przed cook nie ma różniącej się litery, więc pętla obsługująca tylko różnice niczego nie wykrywa i zwraca uporządkowanie. Odpowiedź to "invalid".
Pominięcie liter, które nie pojawiają się w żadnej regule. W pierwszym przykładzie żadna reguła nie wymienia e, a mimo to należy ono do odpowiedzi i w najmniejszym uporządkowaniu znajduje się na początku.
Używanie zwykłej kolejki zamiast kopca minimalnego. Algorytm Kahna z kolejką zwraca poprawne uporządkowanie, ale wymaganiem jest znalezienie najmniejszego.
Dwukrotne zliczenie powtórzonej reguły przy obliczaniu stopnia wejściowego, ale zapisanie jej tylko raz w grafie. Wtedy stopień litery nigdy nie osiąga 0 i poprawna lista zostaje uznana za cykl. Zapisuj każdą regułę tylko raz albo dodawaj ją i usuwaj tyle samo razy.
Uznawanie dwóch identycznych sąsiadujących słów za pułapkę związaną z prefiksem. Słowo, po którym następuje to samo słowo, jest we właściwej kolejności; niemożliwe jest tylko dłuższe słowo poprzedzające swój własny prefiks.

Najczęstsze pytania4

Jaka jest złożoność czasowa problemu obcego słownika?

O(C + k²), gdzie C to łączna liczba znaków w słowach, a k ≤ 26 to liczba różnych liter. Jedno przejście po liście znajduje pierwszą różnicę w każdej sąsiedniej parze, a algorytm Kahna odwiedza najwyżej k² krawędzi. Kopiec minimalny dodaje O(k log k), co jest niewielkie w porównaniu z resztą. Tablica krawędzi zajmuje O(k²) pamięci.

Dlaczego porównywać tylko sąsiednie słowa?

Uporządkowanie jest przechodnie: jeśli każde słowo jest nie większe od następnego, cała lista jest uporządkowana. Zatem każda reguła, którą można odczytać z dwóch odległych słów, wynika już z sąsiadujących par między nimi. Porównywanie każdej pary słów nie wnosi żadnych informacji, a wymaga O(n²) porównań zamiast n-1.

Dlaczego wybranie najmniejszej gotowej litery daje najmniejszy porządek?

Każdy pasujący porządek musi zaczynać się od litery, na którą nie wskazuje żadna reguła. Najmniejsza taka litera jest więc najmniejszą możliwą pierwszą literą, a umieszczenie jej usuwa tylko krawędzie, dzięki czemu każda inna gotowa litera pozostaje dostępna. Powtarzanie tego argumentu na każdej pozycji pozwala zbudować najmniejszy porządek, litera po literze. Kopiec minimalny udostępnia najmniejszą gotową literę w czasie O(log k).

Dlaczego słowo przed własnym prefiksem jest nieprawidłowe?

W każdym alfabecie słowo występuje po swoim własnym przedrostku, ponieważ porównanie kończy się na literach krótszego słowa, zanim znajdzie różnicę. Dlatego cooking przed cook oznacza nieprawidłową kolejność, niezależnie od tego, jakie są litery, i żadna reguła nie może tego naprawić. To jedyny sposób, w jaki lista może być niemożliwa do uporządkowania bez żadnego cyklu wśród jej reguł.

Python

def alienOrder(words):
    # Wpisz kod tutaj

Przypadki testowe

Przypadek 1

Przypadek 2

Przypadek 3

Wejście

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

Oczekiwane

"etacn"