Temu Duga Pengekodan: Bagaimanakah Anda Menyelesaikan Word Ladder dengan BFS Dwi-arah?

Prompt dan Konteks yang Berkenaan

Diberi beginWord, endWord, dan wordList, cari panjang jujukan transformasi yang paling pendek. Setiap pasangan bersebelahan mestilah berbeza pada tepat satu kedudukan, dan setiap perkataan selepas beginWord, termasuk endWord, mestilah muncul dalam kamus. Panjang yang dikembalikan mengira perkataan, bukan perubahan.

beginWord = "hit"
endWord   = "cog"
wordList  = ["hot", "dot", "dog", "lot", "log", "cog"]

One shortest sequence:
hit -> hot -> dot -> dog -> cog

Return: 5

Gunakan kontrak standard: beginWord dan endWord adalah berbeza, semua perkataan mengandungi huruf kecil bahasa Inggeris, setiap perkataan kamus mempunyai panjang yang sama L, entri kamus adalah unik, dan terdapat paling banyak N = 5,000 entri. Jika endWord tiada atau tidak boleh dicapai, kembalikan 0.

Ini ialah soalan graf yang grafnya tersembunyi di dalam rentetan. Setiap perkataan yang sah ialah bucu; dua perkataan berkongsi satu sisi tanpa arah dengan kos unit apabila ia berbeza pada satu kedudukan. Oleh itu, prompt ini meminta laluan terpendek pasangan tunggal dalam graf tanpa wajaran. Bahan temu duga graf awam pada tahun 2026 masih menyenaraikan Word Ladder sebagai masalah transformasi BFS, dan satu akaun temu duga awam Jun 2026 membincangkan varian Word Ladder II yang lebih sukar. Rekod-rekod tersebut membuktikan nilai persediaan semasa; ia tidak membuktikan kekerapan temu duga atau atribusi syarikat yang disahkan, jadi artikel ini tidak membuat sebarang dakwaan tersebut.

Apa yang Dinilai oleh Penemu Duga

Isyarat pertama ialah sama ada calon dapat melihat graf tersirat. Membandingkan setiap pasangan perkataan kamus membina graf yang betul, tetapi menelan kos O(N²L) perbandingan aksara. Jawapan yang lebih kukuh menjana hanya jiran yang mungkin bagi perkataan semasa: gantikan setiap daripada L aksaranya dengan 25 huruf yang lain, kemudian gunakan set cincangan untuk menguji keahlian kamus.

Isyarat kedua ialah hujah laluan terpendek. Setiap transformasi menelan kos satu langkah, jadi BFS meneroka keadaan dalam jarak yang tidak berkurang. DFS akhirnya mungkin menemui laluan tetapi tidak menjadikan laluan pertama sebagai yang terpendek. Dijkstra adalah betul dengan wajaran unit tetapi menambah barisan keutamaan tanpa menambah maklumat.

Isyarat ketiga ialah pemasaan penandaan dilawati. Sesuatu perkataan mesti meninggalkan set belum dilawati apabila ia memasuki sesuatu sempadan, bukan apabila ia dikembangkan kemudian. Penandaan yang ditangguhkan membolehkan banyak nod induk memasukkan perkataan yang sama ke dalam barisan gilir, meningkatkan kedua-dua kerja dan memori. Dengan BFS dwi-arah, jiran yang dijana mesti disemak terhadap sempadan semasa yang bertentangan sebelum ia disemak terhadap set belum dilawati.

Isyarat keempat ialah sama ada pengoptimuman tersebut kekal boleh dibuktikan. BFS dwi-arah mengekalkan satu sempadan peringkat daripada setiap titik akhir dan mengembangkan sempadan yang lebih kecil. Ia sering mengurangkan carian seperti pepohon daripada kira-kira b^d keadaan kepada dua carian berhampiran b^(d/2), dengan b ialah percabangan berkesan dan d ialah jawapan dalam sisi. Ia tidak menambah baik batas asimptotik kes terburuk: kamus adversarial masih boleh menyebabkan algoritma memeriksa hampir setiap perkataan.

Akhir sekali, jawapan yang kukuh menyatakan kos rentetan sebenar. Setiap perkataan yang dikembangkan mencuba paling banyak 25L mutasi. Dalam Python, mencipta rentetan calon menelan kos O(L), jadi pelaksanaan ini mengambil masa jangkaan O(NL²) untuk abjad 26 huruf yang tetap, dengan storan aksara O(NL). Menyebutnya sebagai O(NL) secara senyap menganggap pembinaan rentetan sebagai masa malar.

Soalan Penjelasan Sebelum Menjawab

• Apakah sebenarnya yang dikira oleh nilai pulangan? Kontrak ini mengira kedua-dua titik akhir. Oleh itu, satu transformasi

sah secara langsung mengembalikan 2; API kiraan sisi akan mengembalikan kurang satu.

• Adakah endWord mesti berada dalam kamus? Ya. Jika ia tiada, kembalikan 0 sebelum mencari. Varian

yang membenarkan sasaran berada di luar kamus mengubah peraturan keluar awal ini.

• Adakah semua perkataan mempunyai panjang dan abjad yang sama? Ya: panjang L, huruf kecil bahasa Inggeris. Unicode,

panjang bercampur, atau abjad yang lebih besar mengubah penjanaan jiran dan kosnya.

• Adakah entri unik? Ya. Menukar input kepada set masih berguna untuk keahlian masa malar jangkaan

dan penyingkiran yang dilawati. Jika duplikasi dibenarkan, ia tidak akan mencipta bucu yang berbeza.

• Adakah kita memerlukan satu panjang, satu laluan, atau setiap laluan terpendek? Masalah asas hanya memerlukan panjangnya.

Mengembalikan laluan memerlukan pemetaan induk; mengembalikan setiap laluan terpendek memerlukan pengekalan semua nod induk daripada peringkat BFS yang sama dan tidak boleh menggunakan peraturan pemadaman segera yang sama tanpa perubahan.

• Adakah ini satu pertanyaan atau banyak pertanyaan ke atas kamus yang stabil? Untuk satu pertanyaan, mutasi atas permintaan adalah

mudah dan mengelakkan indeks penuh. Pertanyaan berulang mungkin mewajarkan indeks corak wildcard yang boleh diguna semula.

• Bolehkah beginWord sudah muncul dalam kamus? Ya. Ia masih merupakan satu bucu dan harus dikeluarkan

daripada set belum dilawati semasa permulaan.

Rangka Kerja Jawapan 30 Saat

“Saya memodelkan setiap perkataan sebagai bucu dan menyambungkan dua perkataan apabila ia berbeza pada satu kedudukan. Setiap sisi menelan kos satu transformasi, jadi ini ialah masalah laluan terpendek tanpa wajaran. Saya akan menjalankan BFS dwi-arah daripada beginWord dan endWord, sentiasa mengembangkan sempadan keseluruhan peringkat yang lebih kecil. Bagi setiap perkataan sempadan, saya menjana paling banyak 25L mutasi satu hurufnya dan mengujinya dalam set cincangan. Jika mutasi berada dalam sempadan bertentangan, dua awalan terpendek yang diteroka membentuk jujukan terpendek, jadi saya mengembalikan kiraan perkataan semasa ditambah satu. Jika tidak, saya mengeluarkan perkataan sah yang belum dilihat sebaik sahaja saya menambahnya ke sempadan seterusnya. Jika endWord tiada atau sesuatu sempadan menjadi kosong, saya mengembalikan sifar. Kes terburuk masih melawati perkataan N; disebabkan pembinaan calon dalam Python menyalin L aksara, masa adalah O(NL²) dan kandungan rentetan yang disimpan adalah O(NL). Saya akan menguji kes langsung, tidak boleh dicapai, kitaran, penemuan duplikasi, dan sempadan asimetri.”

Pecahan Langkah demi Langkah

Mulakan dengan model graf. Biarkan set bucu mengandungi setiap perkataan kamus ditambah beginWord. Bagi mana-mana dua perkataan dengan panjang yang sama, tambah satu sisi tepat apabila jarak Hamming keduanya adalah satu. Graf ini adalah tanpa arah: jika hot boleh berubah kepada dot, perubahan sebaliknya juga adalah sah. Ia adalah tanpa wajaran kerana setiap perubahan sah menyumbang satu sisi.

Graf berpasangan eksplisit membandingkan O(N²) pasangan dan menghabiskan O(L) bagi setiap perbandingan. Itu ialah pra-pemprosesan O(N²L) walaupun kebanyakan pasangan tidak berkaitan. Abjad input memberikan ruang calon yang lebih kecil. Sesuatu perkataan mempunyai paling banyak 25L mutasi satu huruf yang berbeza; keahlian kamus menentukan yang mana merupakan bucu sebenar.

BFS satu sisi sudah pun betul. Invariannya ialah:

At the start of level k:
  the frontier contains exactly the discovered words at edge distance k;
  no undiscovered word has distance less than k;
  every word outside unvisited has already been assigned its minimum distance.

BFS mencipta peringkat k + 1 hanya daripada peringkat k. Oleh itu, penemuan pertama sesuatu perkataan menggunakan laluan terpendek. Mengeluarkan perkataan daripada unvisited semasa penemuan mengekalkan fakta tersebut dan menghalang entri sempadan yang bertindih.

Bagi satu sasaran tunggal yang diketahui, cari daripada kedua-dua titik akhir. front ialah satu peringkat lengkap dari sebelah permulaan, dan back ialah satu peringkat lengkap dari sebelah penamat. sequence_length adalah bersamaan dengan jumlah kedalaman sisi semasa mereka ditambah satu, kerana ia mengira perkataan sempadan pada kedua-dua hujung tanpa sisi penyambung lagi. Mengembangkan mana-mana sempadan penuh akan meningkatkan jumlah kedalaman tersebut sebanyak satu. Jika perkataan yang dijana kepunyaan sempadan bertentangan, sisi penyambung menjadikan jawapannya sequence_length + 1.

Mengembangkan sempadan yang lebih kecil mengubah prestasi, bukan ketepatan. Menukar ganti kedua-dua set hanya mengubah lapisan BFS sah mana yang maju seterusnya; setiap set masih mewakili satu kedalaman tepat dari asalnya sendiri. Menyemak persilangan terhadap sempadan semasa yang bertentangan adalah penting. Satu set unvisited global tunggal adalah selamat kerana apabila satu sisi menemui sesuatu perkataan, ia menuntutnya dengan serta-merta. Jika pengembangan kemudian mempunyai sisi ke lapisan yang telah dikembangkan bagi carian yang satu lagi, pengembangan lebih awal itu tentu telah menemui perkataan yang sama terlebih dahulu, jadi carian tidak boleh bersilang secara senyap di belakang sempadan semasa mereka.

ALPHABET = "abcdefghijklmnopqrstuvwxyz"


def ladder_length(
    begin_word: str,
    end_word: str,
    word_list: list[str],
) -> int:
    unvisited = set(word_list)
    if end_word not in unvisited:
        return 0

    front = {begin_word}
    back = {end_word}
    unvisited.discard(begin_word)
    unvisited.remove(end_word)
    sequence_length = 1

    while front and back:
        if len(front) > len(back):
            front, back = back, front

        next_front: set[str] = set()

        for word in front:
            for index, original in enumerate(word):
                for letter in ALPHABET:
                    if letter == original:
                        continue

                    candidate = word[:index] + letter + word[index + 1 :]

                    if candidate in back:
                        return sequence_length + 1

                    if candidate in unvisited:
                        unvisited.remove(candidate)
                        next_front.add(candidate)

        front = next_front
        sequence_length += 1

    return 0

Jejaki sampel mengikut lapisan sempadan:

Algoritma ini mengembangkan bahagian cog yang lebih kecil pada pengembangan 3. Pada pengembangan 4, dot mencapai dog atau lot mencapai log, jadi ia mengembalikan 5. Tertib lelaran set boleh memilih sisi pertemuan terpendek yang berbeza; panjangnya tidak berubah.

Biarkan N menjadi saiz kamus dan L panjang perkataan. Setiap perkataan ditambah ke sempadan paling banyak sekali dan, jika dikembangkan, mencuba 25L calon. Carian cincangan dijangka O(1), tetapi setiap calon hiris-dan-gabung (slice-and-concatenate) Python menelan kos O(L), memberikan masa kes terburuk jangkaan O(NL²) dengan abjad yang tetap. Set menyimpan paling banyak O(N) rujukan dan rentetannya mengandungi O(NL) aksara. Rentetan calon sementara menambah O(L) pada satu-satu masa. Jika sesuatu temu duga menggunakan penimbal aksara lebar tetap boleh ubah dan menganggap penghasilan atau pencincangan calon sebagai O(L), batas teliti yang sama masih terpakai.

Indeks wildcard ialah alternatif utama. Petakan corak seperti h*t, *ot, dan ho* kepada perkataan yang sepadan. Ia boleh diguna semula merentasi banyak pertanyaan dan mengelakkan cubaan huruf yang tiada dalam kamus. Dalam Python, mencipta rentetan corak L untuk perkataan N juga menelan kos kerja aksara O(NL²) dan boleh mengekalkan O(NL) entri baldi. Semasa BFS, kosongkan baldi corak yang telah digunakan atau jejakinya sebagai telah diproses; mengimbas baldi besar yang sama untuk banyak perkataan sebaliknya boleh menghasilkan semula kerja kuadratik. Untuk satu pertanyaan tunggal di bawah kekangan yang dinyatakan, mutasi bersama set mempunyai lebih sedikit bahagian yang bergerak.

Uji kontrak yang boleh dilaksanakan, bukan sekadar sampel:

cases = [
    (
        "hit",
        "cog",
        ["hot", "dot", "dog", "lot", "log", "cog"],
        5,
    ),
    ("hit", "cog", ["hot", "dot", "dog", "lot", "log"], 0),
    ("a", "c", ["a", "b", "c"], 2),
    ("red", "tax", ["ted", "tex", "red", "tax", "tad", "den", "rex", "pee"], 4),
    ("aaa", "bbb", ["aab", "abb", "bbb", "aba", "baa"], 4),
]

for begin_word, end_word, words, expected in cases:
    actual = ladder_length(begin_word, end_word, words)
    assert actual == expected, (begin_word, end_word, actual, expected)

Ujian sifat (property tests) boleh menjana kamus rawak kecil, membina graf berpasangan eksplisit sebagai oracle yang dipercayai, dan membandingkan hasil BFS biasanya dengan fungsi yang dioptimumkan. Kekalkan juga senarai input tanpa perubahan, uji kamus di mana satu sempadan berkembang jauh lebih pantas daripada yang lain, dan sahkan perkataan yang boleh dicapai melalui beberapa nod induk hanya dikembangkan sekali.

Contoh Jawapan Berkualiti Tinggi

“Perkataan-perkataan ini membentuk graf tanpa arah tersirat. Bucu ialah perkataan yang sah, dan satu sisi menghubungkan perkataan dengan jarak Hamming satu. Disebabkan semua sisi menelan kos satu, BFS memberikan bilangan transformasi minimum. Saya akan mengembalikan bilangan perkataan, jadi hit -> hot mempunyai panjang dua.

Mula-mula saya meletakkan kamus ke dalam satu set dan menolak kes di mana endWord tiada. Saya mengekalkan satu sempadan pada setiap titik akhir dan satu set perkataan yang belum ditemui oleh mana-mana carian. Pada setiap lelaran saya mengembangkan sempadan lengkap yang lebih kecil. Bagi setiap perkataan dan kedudukan aksara, saya mencuba 25 huruf kecil yang lain. Saya menyemak calon terhadap sempadan bertentangan terlebih dahulu; padanan menghubungkan dua awalan BFS, jadi jawapannya ialah kiraan perkataan terkumpul ditambah satu. Jika tidak, sekiranya calon belum dilawati, saya mengeluarkannya serta-merta dan menambahnya ke sempadan seterusnya.

Invariannya ialah setiap sempadan adalah tepat satu lapisan jarak dari titik akhirnya, dan setiap perkataan yang dikeluarkan sudah mempunyai jarak minimumnya dari sisi yang menemuinya. Mengembangkan bahagian yang lebih kecil tidak mengubah lapisan-lapisan tersebut. Sambungan sempadan pertama adalah yang terpendek kerana sebarang laluan yang lebih pendek pasti telah menghubungkan dua lapisan yang lebih awal. Penyingkiran segera menghalang penemuan duplikasi.

Paling banyak N perkataan dikembangkan. Setiap satu mencuba 25L mutasi, dan Python menghabiskan O(L) membina setiap calon, jadi saya menyatakan masa jangkaan O(NL²) dan aksara yang disimpan O(NL). Carian dwi-arah biasanya mengurangkan keadaan yang diteroka tetapi mempunyai kes terburuk yang sama. Bagi pertanyaan berulang saya akan mempertimbangkan indeks wildcard yang boleh diguna semula; untuk pertanyaan sekali sahaja ini, mutasi adalah lebih mudah. Saya akan mengesahkan sampel rasmi, sasaran hilang, transformasi langsung, beberapa laluan terpendek, kitaran, dan oracle graf eksplisit rawak.”

Kesilapan Biasa

• Menjalankan DFS dan mengembalikan laluan pertamanya → DFS tidak melawati laluan mengikut kiraan transformasi →

Gunakan BFS kerana setiap sisi mempunyai kos unit.

• Membandingkan setiap pasangan kamus → pembinaan graf menelan kos O(N²L) → **Jana paling banyak 25L

jiran calon bagi setiap perkataan yang dikembangkan.**

• Menandakan perkataan dilawati hanya apabila dikeluarkan (popped) → beberapa nod induk boleh memasukkannya ke dalam barisan gilir → **Keluarkannya daripada

unvisited apabila menambahnya ke sempadan.**

• Hanya menyemak unvisited sebelum sempadan bertentangan → perkataan pertemuan telah pun dikeluarkan

oleh carian yang satu lagi → Uji sempadan semasa yang bertentangan terlebih dahulu.

• Mengembangkan mana-mana sisi yang dinamakan front → satu sisi mungkin meletup manakala sisi yang lain kekal kecil →

Tukar ganti dan kembangkan sempadan keseluruhan peringkat yang lebih kecil.

• Mencampurkan kiraan sisi dengan kiraan perkataan → sampel mengembalikan empat bukannya lima → **Mulakan

kiraan jujukan kepada satu dan tambah perkataan penyambung pada sisi pertemuan.**

• Mendakwa BFS dwi-arah mengubah kerumitan kes terburuk → kamus adversarial yang padat mungkin

masih mendedahkan hampir setiap perkataan → Terangkan faedah faktor percabangan sebagai tipikal, bukan dijamin.

• Memanggil mutasi Python sebagai O(NL) → setiap calon menyalin atau mencincang L aksara → **Nyatakan

model operasi rentetan dan gunakan O(NL²) untuk pelaksanaan ini.**

• Menggunakan semula baldi wildcard tanpa menghabiskannya → senarai besar yang sama diimbas berulang kali →

Kosongkan setiap baldi corak yang diproses atau tandakannya sebagai telah digunakan.

• Menggunakan satu set dilawati global tetapi membenarkan pengembangan peringkat separa → susunan pertemuan dan perakaunan jarak

menjadi sukar untuk dibuktikan → Majukan satu peringkat sempadan lengkap pada satu masa.

• Memetik pengalaman syarikat yang dilaporkan sendiri sebagai atribusi yang disahkan → siaran awam bukanlah

rekod majikan → Kekalkan companyName sebagai null dan gunakan rekod tersebut hanya sebagai bukti awam semasa.

Soalan Susulan dan Cara Mengendalikannya

Susulan 1: Bagaimanakah anda mengembalikan satu jujukan terpendek yang sebenar?

Kekalkan satu peta induk (parent map) bagi setiap arah. Apabila calon ditemui, rekodkan perkataan yang menghasilkannya. Pada sisi pertemuan, telusuri peta induk sebelah permulaan kembali ke beginWord, songsangkan awalan tersebut, kemudian telusuri peta induk sebelah penamat ke arah endWord. Disebabkan pelaksanaan ini boleh menukar ganti pemboleh ubah sempadan, simpan peta induk mengikut arah semantik dan bukannya menganggap front semasa sentiasa merupakan sebelah permulaan. Storan induk ialah rujukan O(N) selain daripada rentetan kamus.

Susulan 2: Apakah yang berubah untuk Word Ladder II, yang mengembalikan setiap jujukan terpendek?

Satu nod induk bagi setiap perkataan tidak mencukupi. BFS tertib peringkat (level-order) biasa selalunya lebih mudah untuk difikirkan: kumpulkan setiap pendahulu yang mencapai sesuatu perkataan pada peringkat minimumnya, dan keluarkan perkataan yang baru ditemui daripada kamus global hanya selepas keseluruhan peringkat selesai. Ini membenarkan berbilang nod induk pada peringkat yang sama tanpa membiarkan laluan yang lebih panjang menambah nod induk kemudian. Berhenti selepas melengkapkan peringkat pertama yang mencapai endWord, kemudian undur jejak (backtrack) melalui DAG pendahulu tersebut. Saiz output boleh menjadi eksponen, jadi kerumitan mesti merangkumi jumlah bilangan dan panjang jujukan yang dikembalikan.

Susulan 3: Bilakah BFS satu sisi biasa lebih diutamakan?

Gunakannya apabila kamus adalah kecil, hanya satu titik akhir diketahui, graf adalah berarah dan jiran songsang memerlukan kos yang tinggi, atau kesederhanaan kod lebih penting daripada mengurangkan sempadan. BFS satu sisi mempunyai lebih sedikit invarian dan menjadikan pembinaan semula induk mudah. Ia mengekalkan penjana jiran yang sama dan batas O(NL²) yang sama untuk perwakilan Python ini.

Susulan 4: Bilakah anda akan membina baldi corak wildcard?

Bina ia apabila banyak pertanyaan berkongsi kamus yang stabil, abjad adalah besar, atau menjana setiap penggantian abjad membazirkan kerja. Versikan indeks dengan kamus, sertakan corak beginWord setiap pertanyaan apabila ia tidak diindeks, dan gunakan setiap baldi paling banyak sekali bagi setiap carian. Pertukarannya ialah masa pra-pemprosesan, memori baldi, dan ketidaksahan apabila perkataan berubah.

Susulan 5: Bagaimana jika perubahan huruf yang berbeza mempunyai kos yang berbeza?

Graf menjadi berwajaran, jadi lapisan BFS tidak lagi mewakili kos minimum. Gunakan Dijkstra untuk kos bukan negatif, menjana jiran tersirat yang sama tetapi menyusun sempadan mengikut kos terkumpul. Heuristik boleh diterima yang sah boleh menyokong A*, tetapi jarak Hamming hanya boleh diterima selepas diskalakan oleh batas bawah yang terbukti bagi kos sebarang perubahan aksara yang tinggal.

Susulan 6: Bagaimana jika abjadnya ialah Unicode atau perkataan mempunyai panjang yang berbeza?

Tentukan operasi yang sah terlebih dahulu. Titik kod Unicode dan kelompok grafem adalah unit yang berbeza, dan operasi sisip atau padam memperkenalkan sisi yang mengubah panjang. Penjanaan penggantian langsung tidak lagi meliputi graf. Bergantung pada kontrak, gunakan carian jiran jarak-suntingan-satu berindeks, trie, atau baldi panjang-dan-corak, serta sertakan peraturan normalisasi dalam kesamarataan dan pencincangan.

Susulan 7: Bagaimanakah anda membuktikan syarat henti dwi-arah dalam temu duga?

Tetapkan setiap sempadan semasa satu kedalaman dari titik akhirnya sendiri. Algoritma ini memajukan tepat satu lapisan kedalaman lengkap bagi setiap lelaran. Sebelum sesuatu pengembangan, sequence_length ialah dua kedalaman sempadan ditambah satu. Oleh itu, sisi yang dijana ke dalam sempadan bertentangan membentuk laluan dengan sequence_length + 1 perkataan. Jika laluan yang lebih pendek wujud, ia akan mengandungi satu sisi antara dua lapisan dengan jumlah kedalaman yang lebih kecil, dan lapisan-lapisan tersebut pasti telah pun dikembangkan dan disambungkan. Itu bercanggah dengan ini sebagai pertemuan sempadan yang pertama.

Susulan 8: Bagaimanakah anda mengesahkan carian yang dioptimumkan selain daripada contoh?

Untuk kamus rawak kecil, sambungkan secara eksplisit setiap pasangan yang jarak Hammingnya adalah satu dan jalankan oracle BFS biasa. Bandingkan jawapan dengan BFS dwi-arah merentasi ribuan kes yang dijana. Tambah invarian bahawa tiada sempadan bersilang dengan unvisited, tiada perkataan ditemui dua kali, dan setiap perkataan sempadan seterusnya berbeza satu aksara daripada perkataan sempadan semasa. Ini memisahkan bukti ketepatan daripada beberapa output yang dipilih sendiri.