Temuduga Pengekodan: Menyelesaikan Alien Dictionary dengan Isihan Topologi

Gesaan dan Konteks yang Berkenaan

Diberikan tatasusunan perkataan words yang mengandungi rentetan ASCII huruf kecil bukan kosong, anggap tatasusunan tersebut didakwa diisih mengikut abjad yang tidak diketahui. Kembalikan sebarang susunan yang mengandungi setiap aksara berbeza dalam input tepat sekali dan menjadikan senarai perkataan tersebut diisih. Kembalikan rentetan kosong apabila tiada susunan sedemikian wujud. Jika beberapa abjad berfungsi, mana-mana satu daripadanya boleh diterima.

Bagi versi temuduga, anggap paling banyak 10,000 perkataan dan paling banyak 100,000 aksara secara keseluruhan. Ini merupakan kekangan latihan, bukan had daripada platform tertentu. Untuk ["wrt", "wrf", "er", "ett", "rftt"], satu jawapan ialah "wertf". Senarai ["abc", "ab"] adalah mustahil kerana perkataan yang lebih panjang mendahului awalannya sendiri. Senarai ["z", "x", "z"] adalah mustahil kerana ia membayangkan kedua-dua z < x dan x < z.

Bahagian yang sukar hadir sebelum isihan topologi. Input membekalkan perkataan yang diisih; sisi graf mesti dideduksikan. Penyelesaian yang betul mesti mendeduksikan dengan tepat kekangan yang dijustifikasikan oleh perbandingan leksikografi, mengekalkan aksara yang tidak mempunyai sisi, dan membezakan awalan tidak sah daripada kitaran berarah.

Perkara yang Dinilai oleh Penemu Duga

Isyarat pertama ialah sama ada calon menerbitkan sisi daripada aksara pertama yang berbeza bagi dua perkataan bersebelahan. Jika "wrt" muncul sebelum "wrf", perbandingan itu membuktikan t < f. Aksara selepas perbezaan pertama itu tidak mendedahkan apa-apa tentang pasangan ini kerana perbandingan leksikografi telah pun diputuskan.

Isyarat kedua ialah penaakulan awalan. Apabila semua aksara yang dibandingkan sepadan, perkataan yang lebih pendek mesti datang dahulu. "ab" sebelum "abc" tidak menambah sisi dan kekal sah; "abc" sebelum "ab" bercanggah dengan setiap abjad yang mungkin. Isihan topologi sahaja tidak dapat menemui percanggahan ini kerana ia tidak mencipta sisi.

Isyarat ketiga ialah pembinaan graf yang lengkap. Setiap aksara yang diperhatikan memerlukan nod, termasuk aksara terpencil daripada input perkataan tunggal. Bukti berulang bagi sisi yang sama tidak boleh menambahkan indegree dua kali. Set bagi setiap nod sumber memastikan keirasan dan indegree konsisten.

Isyarat akhir ialah pembuktian dan pengesahan. Algoritma Kahn mengembalikan susunan lengkap hanya apabila ia mengeluarkan setiap nod. Output yang lebih pendek membuktikan kitaran masih wujud. Pelbagai pilihan ber-indegree sifar bermakna bukti tersebut tidak menentukan satu abjad yang unik; itu sah di bawah kontrak asas dan tidak sepatutnya disalah labelkan sebagai ralat.

Soalan untuk Dijelaskan Sebelum Menjawab

• Adakah input merangkumi setiap aksara dalam abjad? Jawapan ini menyusun setiap aksara yang diperhatikan

dalam perkataan. Ia tidak boleh mencipta atau meletakkan aksara yang tidak kelihatan tanpa takrifan abjad luaran.

• Adakah sebarang susunan sah boleh diterima? Masalah asas menerima mana-mana satu. Memerlukan hasil terkecil di bawah

susunan aksara bahasa hos memerlukan min-heap dan mengubah kerumitan.

• Bagaimanakah ketidakmungkinan harus diwakili? Kontrak ini menggunakan rentetan kosong untuk kedua-dua

awalan tidak sah dan kitaran. API pengeluaran mungkin mengembalikan sebab dan saksi yang berstruktur.

• Apakah itu aksara? Input asas mengandungi huruf ASCII kecil. Titik kod Unicode atau gugusan grafem

memerlukan kontrak pemecahan token (tokenization) sebelum pembinaan graf.

• Bolehkah perkataan berulang? Ya. Perkataan bersebelahan yang sama tidak menambah kekangan. Ia tidak menjadikan kamus tidak sah.
• Adakah abjad mesti unik? Tidak. Soalan susulan boleh mengesan keunikan dengan memeriksa bilangan nod

ber-indegree sifar yang tersedia pada setiap langkah.

• Bolehkah input menjadi kosong? Versi ini memerlukan sekurang-kurangnya satu perkataan bukan kosong. Jika input kosong dibenarkan,

sahkan sama ada hasil yang dijangkakan ialah abjad kosong atau permintaan tidak sah.

Rangka Kerja Jawapan 30 Saat

“Saya akan mencipta nod graf bagi setiap aksara berbeza. Bagi setiap pasangan perkataan bersebelahan, saya mengimbas sehingga perbezaan pertama; itu memberikan satu sisi berarah daripada aksara perkataan terdahulu kepada aksara perkataan terkemudian. Jika tiada perbezaan dan perkataan terdahulu lebih panjang, susunan awalan adalah mustahil, jadi saya mengembalikan rentetan kosong. Saya menyahduplikasi sisi sambil mengekalkan indegree, kemudian menjalankan isihan topologi Kahn daripada semua aksara ber-indegree sifar. Jika saya memproses setiap nod, hasilnya mematuhi setiap perbandingan yang dideduksikan; jika saya memproses kurang nod, kitaran menjadikan kamus tidak konsisten. Jumlah masa adalah linear mengikut aksara input ditambah graf, dan berbilang susunan topologi yang sah boleh diterima.”

Perincian Langkah demi Langkah

Biarkan C sebagai jumlah keseluruhan aksara merentas semua perkataan, U sebagai bilangan aksara berbeza, dan E sebagai bilangan sisi keutamaan yang berbeza. Mulakan graph[ch] sebagai set dan indegree[ch] sebagai sifar bagi setiap aksara yang ditemui. Permulaan ini perlu sebelum membandingkan perkataan: sesuatu aksara boleh jadi sah dan tidak dikekang, jadi titik hujung sisi sahaja tidak mentakrifkan set nod.

Bandingkan hanya perkataan bersebelahan. Perbandingan bersebelahan adalah mencukupi kerana membuktikan setiap pasangan jiran tersusun akan membuktikan keseluruhan senarai tersusun secara transitiviti. Ia juga mengelakkan bilangan perbandingan pasangan perkataan yang kuadratik. Bagi pasangan first dan second, periksa kedudukan sepadan sehingga panjang yang lebih pendek:

1. Pada ketidakpadanan pertama first[i] != second[i], tambah first[i] -> second[i] dan berhenti membandingkan pasangan tersebut.
2. Jika setiap kedudukan yang dikongsi sepadan dan first lebih panjang, kembalikan rentetan kosong.
3. Jika setiap kedudukan yang dikongsi sepadan dan first tidak lebih panjang, jangan tambah sebarang sisi.

Hanya sisi yang baru dimasukkan akan meningkatkan indegree destinasi. Andaikan kedua-dua "za" < "zb" dan "ca" < "cb" membayangkan a -> b. Mengira sisi itu dua kali akan menyebabkan b mempunyai indegree positif selepas a dikeluarkan dan secara palsu melaporkan kitaran.

Algoritma Kahn meletakkan setiap aksara ber-indegree sifar ke dalam baris gilir (queue). Invarian algoritma ini ialah: bagi setiap aksara yang belum diproses, indegree adalah sama dengan bilangan sisi masuk daripada aksara lain yang belum diproses; baris gilir mengandungi tepat aksara yang tidak mempunyai pendahulu sedemikian. Mengeluarkan aksara dalam baris gilir adalah selamat. Mengurangkan setiap jiran keluar memodelkan penyingkiran sisi tersebut, dan jiran memasuki baris gilir apabila pendahulu terakhirnya yang belum dipenuhi hilang.

from collections import deque


def alien_order(words: list[str]) -> str:
    graph = {char: set() for word in words for char in word}
    indegree = {char: 0 for char in graph}

    for first, second in zip(words, words[1:]):
        limit = min(len(first), len(second))

        for index in range(limit):
            before = first[index]
            after = second[index]
            if before == after:
                continue

            if after not in graph[before]:
                graph[before].add(after)
                indegree[after] += 1
            break
        else:
            if len(first) > len(second):
                return ""

    ready = deque(
        char for char, degree in indegree.items() if degree == 0
    )
    order: list[str] = []

    while ready:
        char = ready.popleft()
        order.append(char)

        for neighbor in graph[char]:
            indegree[neighbor] -= 1
            if indegree[neighbor] == 0:
                ready.append(neighbor)

    return "".join(order) if len(order) == len(indegree) else ""

Bukti ini mempunyai dua lapisan. Pertama, pengekstrakan graf adalah kukuh: setiap sisi datang daripada ketidakpadanan pertama bagi pasangan bersebelahan, jadi setiap abjad yang sah mesti mematuhinya. Semakan awalan mengeluarkan satu-satunya kes bersebelahan yang mana tiada ketidakpadanan wujud tetapi susunan adalah mustahil. Kedua, isihan topologi adalah kukuh: invarian baris gilir memastikan setiap aksara output muncul selepas semua pendahulu yang dideduksikan. Oleh itu, setiap pasangan perkataan bersebelahan adalah tersusun, yang menjadikan senarai penuh tersusun.

Jika algoritma mengeluarkan kurang daripada U aksara, setiap nod yang tinggal mempunyai indegree positif. Bermula daripada mana-mana nod yang tinggal dan berulang kali mengikut sisi masuk pasti akan melawat semula nod dalam graf terhingga; segmen yang berulang ialah kitaran berarah. Tiada abjad linear yang dapat memenuhi kitaran tersebut. Sebaliknya, graf asiklik sentiasa mempunyai nod ber-indegree sifar, jadi algoritma Kahn akhirnya mengeluarkan semua nod dan mengembalikan susunan yang sah.

Membina semua nod dan mengimbas perkataan bersebelahan mengambil masa O(C). Setiap nod dan sisi berbeza diproses sekali oleh algoritma Kahn, jadi jumlah masa ialah O(C + U + E) dan ruang tambahan ialah O(U + E). Dengan ASCII huruf kecil, U adalah paling banyak 26, tetapi mengekalkan batas simbolik menjadikan penaakulan ini boleh digunakan semula.

Pengesahan harus memeriksa sifat apabila berbilang jawapan boleh didapati. Hasil bukan kosong mesti mengandungi aksara input berbeza tepat sekali. Bagi setiap pasangan bersebelahan, bandingkannya menggunakan peta kedudukan yang dikembalikan dan sahkan ia tersusun; secara berasingan sahkan tiada perkataan yang lebih panjang mendahului awalannya. Uji satu perkataan, perkataan berulang, aksara terpencil, bukti sisi pendua, awalan sah, awalan tidak sah, kitaran, rantai, dan graf dengan beberapa nod ber-indegree sifar.

DFS dengan status putih, kelabu, dan hitam ialah alternatif yang betul. Ia mengesan kitaran melalui sisi ke nod kelabu dan membalikkan postorder untuk hasilnya. Algoritma Kahn menjadikan kekaburan kelihatan melalui set sedia (ready set) dan mengelakkan kebimbangan kedalaman rekursi, jadi ia adalah cadangan yang lebih jelas untuk kontrak ini.

Contoh Jawapan Berkualiti Tinggi

“Saya perlu terlebih dahulu mendeduksikan susunan separa daripada perkataan yang diisih. Saya mencipta nod bagi setiap aksara, termasuk aksara yang tidak pernah mengambil bahagian dalam sesuatu sisi. Bagi setiap pasangan berjiran, saya mengimbas sehingga ketidakpadanan pertama. Jika pasangan itu ialah wrt dan wrf, saya menambah t -> f dan berhenti kerana kedudukan terkemudian tidak boleh menjejaskan perbandingan tersebut. Jika tiada ketidakpadanan dan perkataan pertama lebih panjang, seperti abc sebelum ab, input sudah pun tidak konsisten.

Saya menyimpan jiran dalam set supaya bukti berulang bagi satu hubungan hanya meningkatkan indegree sekali. Kemudian saya menjalankan algoritma Kahn: masukkan semua aksara ber-indegree sifar ke dalam baris gilir, keluarkan satu ke dalam jawapan, kurangkan jiran keluarnya, dan masukkan jiran ke dalam baris gilir apabila indegree-nya mencapai sifar. Invarian adalah bahawa aksara dalam baris gilir tidak mempunyai pendahulu yang tinggal dalam kalangan aksara yang belum diproses, jadi setiap aksara yang dikeluarkan adalah selamat.

Jika panjang output bersamaan dengan bilangan aksara berbeza, setiap sisi yang dideduksikan dipatuhi. Sisi-sisi tersebut ditambah semakan awalan menjadikan setiap pasangan perkataan bersebelahan tersusun, jadi keseluruhan senarai tersusun. Jika panjangnya lebih pendek, baki graf mengandungi kitaran dan tiada abjad yang berfungsi. Masa larian ialah O(C + U + E) dengan ruang O(U + E). Saya akan menguji perkataan yang lebih panjang sebelum awalannya, kitaran dua sisi, bukti pendua bagi satu sisi, perkataan tunggal, dan kes dengan beberapa output sah; untuk kes terakhir saya akan mengesahkan sifat susunan dan bukannya menjangkakan satu rentetan sahaja.”

Kesilapan Biasa

• Menggunakan setiap kedudukan berbeza dalam pasangan perkataan → kedudukan terkemudian tidak mengambil bahagian sebaik sahaja

ketidakpadanan pertama menentukan susunan leksikografi → tambah hanya sisi ketidakpadanan pertama dan berhenti.

• Hanya menjalankan isihan topologi → "abc" sebelum "ab" tidak mencipta sisi dan terlepas → **semak

percanggahan perkataan-lebih-panjang-sebelum-awalan semasa perbandingan pasangan.**

• Mencipta nod hanya semasa menambah sisi → aksara terpencil hilang daripada jawapan → **mulakan

nod bagi setiap aksara yang diperhatikan.**

• Meningkatkan indegree bagi sisi pendua → nod sah tidak pernah mencapai sifar → **gunakan set keirasan

dan tingkatkan hanya pada pemasukan pertama.**

• Mengembalikan hasil separa apabila baris gilir kosong → kekangan kitaran kelihatan berjaya → **wajibkan

panjang output sama dengan kiraan aksara berbeza.**

• Menuntut satu jawapan tetap → susunan separa sah boleh mempunyai beberapa sambungan linear → **uji

susunan yang dikembalikan terhadap aksara, sisi, dan perbandingan perkataan.**

• Membandingkan setiap pasangan perkataan → kerja boleh menjadi kuadratik mengikut kiraan perkataan → **perbandingan

bersebelahan adalah mencukupi untuk mewujudkan susunan terisih.**

• Mendakwa kekaburan bermaksud input tidak sah → berbilang abjad boleh menjelaskan bukti yang sama → **kembalikan

sebarang susunan sah melainkan keunikan adalah sebahagian daripada kontrak.**

Soalan Susulan dan Maklum Balas

Susulan 1: Bagaimanakah anda menentukan sama ada abjad itu unik?

Semasa algoritma Kahn, periksa set sedia sebelum setiap penyingkiran. Jika ia pernah mengandungi lebih daripada satu aksara, sekurang-kurangnya dua pilihan boleh ditukar menjadi susunan topologi sah yang berbeza, jadi buktinya adalah kabur. Jika ia sentiasa mengandungi tepat satu aksara dan setiap nod diproses, susunannya adalah unik. Set sedia yang kosong sebelum selesai masih bermaksud terdapat kitaran.

Susulan 2: Bagaimanakah anda mengembalikan hasil sah terkecil di bawah susunan aksara biasa?

Gantikan baris gilir dengan min-heap yang menggunakan susunan aksara bahasa hos sebagai kuncinya. Memilih aksara sah terkecil pada masa itu menghasilkan sambungan linear terkecil melalui argumen pertukaran tamak (greedy exchange). Masanya menjadi O(C + E + U log U); nyatakan dengan jelas bahawa pemutus seri ini adalah luaran kepada abjad alien.

Susulan 3: Bagaimanakah anda mengembalikan penjelasan yang berguna untuk input tidak sah?

Bagi percanggahan awalan, kembalikan dua perkataan bersebelahan dan indeksnya. Bagi kitaran, jalankan DFS tiga warna pada baki graf selepas Kahn terhenti, simpan penunjuk induk (parent pointers), dan bina semula aksara yang membentuk satu kitaran sisi-belakang (back-edge). Hasil berstruktur boleh membezakan invalid_prefix, cycle, dan valid tanpa membebankan (overloading) rentetan kosong.

Susulan 4: Bolehkah anda memproses senarai perkataan sebagai strim?

Simpan perkataan sebelumnya, tambah nod daripada setiap perkataan baharu, dan deduksikan satu kekangan pasangan bersebelahan apabila perkataan seterusnya tiba. Graf dan indegree masih memerlukan storan sehingga strim tamat kerana bukti terkemudian boleh menambah pendahulu atau mencipta kitaran. Jalankan isihan topologi hanya selepas semua perkataan diperhatikan melainkan sumber membekalkan sempadan pemuktamadan.

Susulan 5: Bagaimanakah anda menyenaraikan (enumerate) setiap abjad yang sah?

Jalankan jejak ke belakang (backtrack) ke atas semua aksara ber-indegree sifar semasa. Pilih satu, buang sisi keluarnya, lakukan rekursi, kemudian pulihkan keadaan. Ini hanya menyenaraikan susunan yang sah, tetapi output boleh menghampiri U!; sahkan abjad yang kecil atau had output sebelum melaksanakannya.

Susulan 6: Apakah yang berubah untuk perkataan Unicode?

Tentukan unit perbandingan terlebih dahulu. Titik kod tidak selalu sepadan dengan aksara yang dilihat pengguna, dan penyusunan tempat setempat (locale collation) boleh mengendalikan bentuk ternormal atau jujukan berbilang titik kod secara khusus. Bahagikan setiap perkataan kepada token mengikut simbol abjad yang dinyatakan, normalkan hanya jika kontrak memerlukannya, kemudian jalankan algoritma graf yang sama ke atas token. Tanpa kontrak tersebut, “susunan aksara” adalah kurang ditentukan secara khusus.