Alien Dictionary

+10

Sebuah daftar kata diurutkan berdasarkan alfabet yang tidak kamu ketahui: 26 huruf kecil bahasa Inggris dalam urutan rahasia tertentu. Kata-kata dibandingkan seperti biasa. Posisi pertama tempat dua kata berbeda menentukan urutannya, dan jika salah satu kata merupakan awalan kata lainnya, kata yang lebih pendek berada lebih dahulu.

Kembalikan huruf-huruf yang muncul dalam kata-kata tersebut sebagai satu string dalam urutan alfabet. Jika ada beberapa urutan yang cocok, kembalikan urutan yang muncul lebih dahulu dalam urutan kamus biasa. Jika tidak ada urutan yang cocok, kembalikan "invalid".

Fungsi

alienOrder(words: string-array) → string

wordsstring-array: kata-kata, diurutkan berdasarkan alfabet yang tidak diketahui
Mengembalikanstring: huruf-huruf dalam urutan terkecil yang sesuai, atau "invalid"

Batasan

1 ≤ words.length ≤ 5000
1 ≤ words[i].length ≤ 10
Setiap kata hanya berisi huruf kecil bahasa Inggris.
Kata yang sama mungkin muncul lebih dari sekali.

Contoh

Input: words = ["tea", "ten", "ate", "act", "cat"]
Output: "etacn"
Penjelasan: tea sebelum ten menempatkan a sebelum n. Pasangan lainnya menghasilkan t sebelum a, t sebelum c, dan a sebelum c. Tidak ada aturan yang menyebut e, jadi urutan terkecil dimulai dengannya: e, t, a, c, n.

Input: words = ["bat", "tab", "tub", "bus"]
Output: "invalid"
Penjelasan: bat sebelum tab menempatkan b sebelum t, dan tub sebelum bus menempatkan t sebelum b. Keduanya tidak mungkin berlaku, jadi tidak ada urutan yang cocok.

Input: words = ["cooking", "cook"]
Output: "invalid"
Penjelasan: cook adalah awal dari cooking, jadi dalam setiap alfabet, kata ini muncul lebih dahulu. Daftar itu menempatkannya di urutan kedua, yang tidak dapat dijelaskan oleh urutan huruf apa pun.

Pertanyaan lanjutan

Bagaimana kamu mengetahui apakah urutan pemasangan itu satu-satunya?

Petunjuk

Buka satu per satu. Setiap petunjuk mengungkap sedikit lebih banyak.

0 dari 3 dibuka

Solusi

Setiap pasangan kata yang bersebelahan menghasilkan paling banyak satu aturan, pada posisi pertama tempat keduanya berbeda: huruf x sebelum huruf y. Urutan yang sesuai adalah urutan topologis dari aturan-aturan tersebut. Siklus, atau kata yang ditempatkan sebelum prefiksnya sendiri, membuat daftar ini mustahil. Min-heap yang selalu menempatkan huruf terkecil yang siap akan menghasilkan urutan terkecil.

Coba setiap urutan huruf

Benar, tetapi tidak selesai pada tes terbesar

Intuisi

Uji satu susunan dari k huruf berbeda dengan memeriksa setiap pasangan yang bersebelahan. Pada posisi pertama yang berbeda, huruf pada kata pertama harus muncul lebih awal; jika tidak ada perbedaan, kata pertama tidak boleh lebih panjang. Telusuri susunan secara berurutan mulai dari susunan alfabetis dengan permutasi berikutnya, dan susunan pertama yang lolos adalah urutan terkecil yang sesuai.

k huruf memiliki k! susunan: 10 menghasilkan 3,628,800 dan 26 menghasilkan sekitar 4 × 10^26, sementara setiap pengujian membaca hingga 5 × 10^4 karakter. Jika tidak ada yang sesuai, pencarian mencoba semuanya.

Algoritma

Kumpulkan huruf-huruf yang berbeda, lalu urutkan secara alfabetis.
Catat peringkat setiap huruf dalam susunan saat ini.
Periksa setiap pasangan yang bersebelahan: pada posisi pertama yang berbeda, huruf pada kata pertama harus memiliki peringkat lebih kecil; jika tidak ada perbedaan, kata pertama tidak boleh lebih panjang.
Jika semua pasangan memenuhi aturan, kembalikan susunan tersebut; jika tidak, lanjutkan ke susunan lebih besar berikutnya.
Jika tidak ada susunan berikutnya, kembalikan "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"

Algoritma Kahn dengan min-heap

Intuisi

Pada sepasang kata yang bersebelahan, hanya perbedaan pertama yang dihitung: act sebelum cat menunjukkan bahwa a mendahului c, dan huruf-huruf setelahnya tidak pernah dibandingkan. Jadi, setiap pasangan menghasilkan paling banyak satu sisi.

Algoritma Kahn mengubah sisi-sisi menjadi urutan: hitung sisi masuk untuk setiap huruf, tempatkan huruf yang jumlahnya 0, hapus sisi-sisi keluarnya, lalu ulangi. Huruf pada siklus selalu memiliki sisi masuk dari huruf sebelumnya pada siklus, sehingga tidak pernah ditempatkan. Jika jumlah huruf yang ditempatkan lebih sedikit daripada jumlah huruf yang muncul, jawabannya adalah "invalid".

Simpan huruf-huruf yang siap dalam min-heap dan tempatkan huruf terkecil. Setiap urutan yang sesuai dimulai dengan huruf yang siap, jadi inilah huruf pertama terkecil yang mungkin. Menempatkannya hanya menghapus sisi, jadi tidak menghalangi huruf lain. Pada contoh pertama, e dan t siap di awal, dan e ditempatkan lebih dulu. Antrean biasa menghasilkan urutan yang valid, tetapi belum tentu urutan terkecil.

Algoritma

Tandai setiap huruf yang muncul dalam kata-kata.
Untuk setiap pasangan kata yang bersebelahan, cari posisi pertama yang berbeda dan tambahkan sisi antara kedua hurufnya, satu kali. Jika tidak ada perbedaan dan kata pertama lebih panjang, kembalikan "invalid".
Hitung sisi masuk dan masukkan setiap huruf yang ditandai dengan jumlah 0 ke min-heap.
Keluarkan huruf terkecil dan tambahkan ke hasil. Kurangi jumlah setiap huruf yang ditunjuknya, lalu masukkan huruf yang jumlahnya menjadi 0.
Kembalikan huruf yang telah ditempatkan jika semua huruf yang ditandai telah ditempatkan, jika tidak, kembalikan "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)

Jebakan dan kasus tepi

Mengambil lebih dari satu aturan dari sepasang kata. Membaca posisi kedua dari act dan cat menambahkan c sebelum a, sehingga contoh pertama menjadi siklus palsu.
Melewatkan jebakan prefiks. cooking sebelum cook tidak memiliki huruf yang berbeda, sehingga perulangan yang hanya menangani perbedaan akan mengembalikan suatu urutan.
Tidak menyertakan huruf yang tidak muncul dalam aturan mana pun. Dalam contoh pertama, tidak ada aturan yang menyebut e, tetapi e tetap harus ada dalam jawaban.
Menghitung aturan yang berulang dua kali dalam derajat masuk, tetapi hanya menyimpannya sekali. Huruf itu tidak pernah mencapai 0, dan daftar yang valid dilaporkan sebagai siklus.
Menganggap dua kata sama yang bersebelahan sebagai jebakan prefiks; kata yang berulang tetap berurutan.

Pertanyaan yang sering diajukan3

Berapa kompleksitas waktu Alien Dictionary?

O(C + k²), dengan C sebagai jumlah total karakter dan k ≤ 26 sebagai jumlah huruf yang berbeda. Satu kali penelusuran pada list menemukan setiap perbedaan pertama, dan algoritma Kahn menelusuri paling banyak k² edge. Tabel edge memerlukan ruang O(k²).

Mengapa hanya membandingkan kata-kata yang bersebelahan?

Urutan terurut bersifat transitif: jika setiap kata tidak lebih besar daripada kata berikutnya, seluruh list sudah terurut. Jadi, aturan apa pun yang dapat kamu simpulkan dari dua kata yang berjauhan sudah mengikuti pasangan kata yang bersebelahan di antaranya.

Mengapa sebuah kata yang muncul sebelum awalan katanya sendiri tidak valid?

Dalam setiap alfabet, sebuah kata muncul setelah prefiksnya sendiri karena perbandingan kehabisan huruf pada kata yang lebih pendek sebelum menemukan perbedaan. Inilah satu-satunya cara sebuah list bisa mustahil tanpa adanya siklus di antara aturan-aturannya.

def alienOrder(words):
    # Tulis kodemu di sini

Tes #1

Tes #2

Tes #3

Argumen

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

Output yang diharapkan

"etacn"