Word Ladder

Q: Apa kompleksitas waktu Word Ladder?

Dengan bucket wildcard, biayanya adalah O(n × L²) untuk n kata dengan panjang L : setiap kata memiliki L pola yang terdiri dari L huruf. Membandingkan setiap pasangan kata membutuhkan biaya O(n² × L) , dan mencoba setiap rantai dengan pencarian mendalam terlebih dahulu membutuhkan waktu eksponensial.

SulitGraf Queue

+10

Kamu mendapatkan dua kata, beginWord dan endWord, serta sebuah daftar kata wordList. Sebuah rangkaian dimulai dengan beginWord, berakhir dengan endWord, dan mengubah tepat satu huruf dari setiap kata ke kata berikutnya. Setiap kata setelah beginWord harus berasal dari wordList, jadi endWord harus ada di dalamnya; beginWord tidak harus ada.

Kembalikan jumlah kata dalam rangkaian terpendek, termasuk kedua ujungnya, atau 0 jika tidak ada.

Fungsi

ladderLength(beginWord: string, endWord: string, wordList: string-array) → integer

beginWordstring: kata pertama pada tangga
endWordstring: kata the ladder harus sampai
wordListstring-array: kata-kata yang harus menjadi sumber bagi setiap langkah berikutnya
Mengembalikaninteger: jumlah kata dalam tangga terpendek, atau 0 jika tidak ada

Batasan

1 ≤ beginWord.length ≤ 10
endWord dan setiap kata dalam wordList memiliki panjang yang sama dengan beginWord.
1 ≤ wordList.length ≤ 5000
Semua kata hanya berisi huruf bahasa Inggris kecil.
beginWord != endWord
Kata-kata dalam wordList semuanya berbeda. beginWord mungkin termasuk di dalamnya atau mungkin tidak.

Contoh

Input: beginWord = "lead"endWord = "gold"wordList = ["load", "goad", "gold", "lend", "lewd", "bold"]
Output: 4
Penjelasan: lead dan gold berbeda dalam tiga huruf, jadi ladder membutuhkan setidaknya 4 kata, dan lead, load, goad, gold berisi 4 kata. lend dan lewd adalah jalan buntu.

Input: beginWord = "cat"endWord = "dog"wordList = ["cot", "cog", "dot", "dig"]
Output: 0
Penjelasan: cat, cot, cog hanya berbeda satu huruf dari dog, tetapi dog tidak ada dalam daftar, jadi tidak ada tangga yang bisa berakhir di sana.

Input: beginWord = "ab"endWord = "cd"wordList = ["ab", "cb", "cd", "ad"]
Output: 3
Penjelasan: ab, ad, cd dan ab, cb, cd masing-masing terdiri dari 3 kata. ab juga ada di dalam daftar, tetapi bagian awal dihitung satu kali.

Pertanyaan lanjutan

Bisakah kamu mengembalikan satu rangkaian kata terpendek itu sendiri, dengan kata-kata berurutan, bukan panjangnya?

Petunjuk

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

0 dari 3 dibuka

Solusi

Anggap kata-kata sebagai simpul dalam graf, dengan sisi di antara kata-kata yang berbeda satu huruf. Setiap sisi memiliki biaya yang sama, jadi pencarian breadth-first menemukan tangga terpendek. Bagian tersulitnya adalah menemukan sisi dengan cepat. Di bawah ini, n adalah jumlah kata dan L panjangnya.

Coba telusuri setiap tangga dengan pencarian mendalam terlebih dahulu

Benar, tetapi tidak selesai pada tes terbesar

Intuisi

Dari kata saat ini, coba setiap kata yang belum digunakan dan berbeda satu huruf, lalu lanjutkan pencarian, dengan tetap mempertahankan panjangnya saat mencapai endWord. Tandai kata-kata di jalur sebagai sudah digunakan, lalu bebaskan kembali saat kamu mundur. Setelah ada rangkaian yang terdiri dari best kata, berhenti memperpanjang jalur yang terdiri dari best-1 kata.

Cara ini mencoba setiap rangkaian tanpa kata yang berulang, dan rangkaian terpendek tidak pernah mengulang kata: menghapus bagian di antara dua kemunculan kata yang sama akan memperpendek rangkaian.

Ke-26 kata aaa, baa hingga zaa semuanya berbeda satu huruf, dan dapat diurutkan dengan sekitar 4 × 10^26 cara. Jika endWord tidak dapat dijangkau, pemangkasan tidak pernah terjadi dan pencarian mencoba semuanya.

Algoritma

Tandai beginWord sebagai sudah digunakan jika ada dalam list, lalu tetapkan best ke 0.
search(word, length): saat mencapai endWord, pertahankan length jika nilainya lebih baik daripada best, lalu kembalikan. Jika best sudah ditetapkan dan length + 1 ≥ best, kembalikan.
Jika tidak, untuk setiap kata yang belum digunakan dan berbeda satu huruf, tandai kata tersebut, panggil search(next, length + 1), lalu hapus tandanya.
Kembalikan best setelah search(beginWord, 1).

def ladderLength(beginWord, endWord, wordList):
    def one_letter_apart(a, b):
        differences = 0
        for x, y in zip(a, b):
            if x != y:
                differences += 1
                if differences > 1:
                    return False
        return differences == 1

    best = 0  # words in the shortest sequence found so far, 0 while there is none
    used = [word == beginWord for word in wordList]  # words on the current path

    def search(word, length):
        nonlocal best
        if word == endWord:
            if best == 0 or length < best:
                best = length
            return
        if best != 0 and length + 1 >= best:
            return  # any longer path cannot beat the best one
        for i, candidate in enumerate(wordList):
            if not used[i] and one_letter_apart(word, candidate):
                used[i] = True
                search(candidate, length + 1)
                used[i] = False  # free the word for other paths

    search(beginWord, 1)
    return best

Pencarian breadth-first, membandingkan setiap pasangan

Benar, tetapi tidak selesai pada tes terbesar

Intuisi

Antrean menelusuri kata berdasarkan urutan jarak: semua kata pada jarak d keluar dari antrean sebelum kata mana pun pada jarak d + 1. Jadi, saat sebuah kata pertama kali dicapai pada jarak d, semua kata yang lebih dekat sudah ditelusuri, dan tangga yang lebih pendek ke kata itu pasti akan mencapainya lebih dahulu. Jaraknya sudah final begitu kata itu masuk ke antrean, jadi tandai kata itu sebagai sudah dikunjungi saat itu, dan saat endWord pertama kali muncul, jaraknya adalah jawabannya.

Versi ini menemukan tetangga sebuah kata dengan membandingkannya dengan setiap kata dalam daftar, lalu berhenti saat menemukan perbedaan kedua: O(n² × L), hingga 25 juta perbandingan kata untuk 5.000 kata.

Algoritma

Jika endWord tidak ada di wordList, kembalikan 0.
Masukkan beginWord ke dalam antrean dengan panjang 1, tandai sebagai sudah dikunjungi jika kata itu ada di dalam daftar.
Ambil kata berikutnya dan bandingkan dengan setiap kata yang belum dikunjungi. Untuk setiap kata yang berbeda satu huruf: jika kata itu adalah endWord, kembalikan panjang + 1; jika tidak, tandai kata itu dan masukkan ke antrean dengan panjang + 1.
Jika antrean kosong, kembalikan 0.

from collections import deque


def ladderLength(beginWord, endWord, wordList):
    def one_letter_apart(a, b):
        differences = 0
        for x, y in zip(a, b):
            if x != y:
                differences += 1
                if differences > 1:
                    return False
        return differences == 1

    if endWord not in wordList:
        return 0
    visited = [word == beginWord for word in wordList]
    queue = deque([(beginWord, 1)])  # (word, words in the sequence up to it)
    while queue:
        word, length = queue.popleft()
        # Compare against every word to find the neighbours.
        for i, candidate in enumerate(wordList):
            if not visited[i] and one_letter_apart(word, candidate):
                if candidate == endWord:
                    return length + 1
                visited[i] = True
                queue.append((candidate, length + 1))
    return 0

Pencarian breadth-first dengan bucket wildcard

Intuisi

Dua kata memiliki selisih tepat satu huruf jika keduanya menjadi sama setelah posisi yang sama disembunyikan: hot dan hit sama-sama menjadi h*t. Buat L pola untuk setiap kata, satu pola untuk setiap posisi yang disembunyikan, lalu masukkan kata itu ke bucket untuk setiap pola. Tetangga sebuah kata adalah kata-kata lain di bucket L-nya, yang ditemukan melalui L pencarian hash, bukan dengan menelusuri seluruh list.

Pada contoh pertama, l*ad berisi load dan le*d berisi lend serta lewd, jadi level 2 terdiri dari ketiga kata itu; lalu *oad menghasilkan goad, dan go*d menghasilkan gold di level 4.

Setelah sebuah bucket ditelusuri, setiap kata di dalamnya sudah dijangkau, jadi kosongkan bucket itu: bucket 26 kata *aa ditelusuri sekali, bukan 26 kali. Biayanya adalah waktu dan ruang O(n × L²), sekitar 500.000 langkah huruf untuk 5.000 kata yang masing-masing terdiri dari 10 huruf.

Algoritma

Jika endWord tidak ada di wordList, kembalikan 0.
Masukkan setiap kata, termasuk beginWord, ke dalam bucket untuk setiap pola L-nya.
Masukkan beginWord ke antrean, tandai sudah dikunjungi, dan tetapkan panjang 1.
Untuk setiap kata pada suatu level: jika kata itu adalah endWord, kembalikan panjangnya. Jika tidak, pindahkan setiap kata yang belum dikunjungi dari setiap bucket polanya ke level berikutnya, tandai sudah dikunjungi, lalu kosongkan bucket tersebut.
Tambahkan 1 ke panjang pada setiap level. Jika antrean habis, kembalikan 0.

from collections import defaultdict, deque


def ladderLength(beginWord, endWord, wordList):
    if endWord not in wordList:
        return 0
    size = len(beginWord)
    # "h*t" -> every word that matches it: hot, hat, hit... are one letter apart.
    buckets = defaultdict(list)
    for word in set(wordList) | {beginWord}:
        for i in range(size):
            buckets[word[:i] + "*" + word[i + 1:]].append(word)
    visited = {beginWord}
    queue = deque([beginWord])
    length = 1  # words in the sequence up to the current level
    while queue:
        for _ in range(len(queue)):  # one level: every word at this distance
            word = queue.popleft()
            if word == endWord:
                return length
            for i in range(size):
                pattern = word[:i] + "*" + word[i + 1:]
                for neighbour in buckets[pattern]:
                    if neighbour not in visited:
                        visited.add(neighbour)
                        queue.append(neighbour)
                buckets[pattern] = []  # all of them are visited now: never scan it again
        length += 1
    return 0

Jebakan dan kasus tepi

Menghitung perubahan, bukan kata. Dari lead ke gold perlu 3 perubahan dan 4 kata, jadi jawabannya 4.
Melewatkan pemeriksaan apakah endWord ada di wordList. Contoh kedua mencapai cog, yang berbeda satu huruf dari dog, tetapi jawabannya 0.
Menandai kata sebagai sudah dikunjungi saat kata itu keluar dari antrean. Kata dalam bucket *aa kemudian dapat masuk hingga 25 kali, sehingga antrean bertambah jauh melampaui n.
Melakukan rekursi sepanjang rantai kata. Rantai terpendek bisa terdiri dari ribuan kata, cukup panjang untuk meluapkan tumpukan pemanggilan.

Pertanyaan yang sering diajukan3

Apa kompleksitas waktu Word Ladder?

Dengan bucket wildcard, biayanya adalah O(n × L²) untuk n kata dengan panjang L: setiap kata memiliki L pola yang terdiri dari L huruf. Membandingkan setiap pasangan kata membutuhkan biaya O(n² × L), dan mencoba setiap rantai dengan pencarian mendalam terlebih dahulu membutuhkan waktu eksponensial.

Bagaimana cara menemukan kata-kata yang hanya berbeda satu huruf?

Bucket wildcard adalah salah satu cara. Cara lainnya adalah mengganti setiap posisi dengan masing-masing dari 26 huruf, lalu mencari hasilnya di hash set yang berisi kata-kata tersebut: 26 × L pencarian untuk L huruf per kata, totalnya O(n × 26 × L²). Keduanya lebih baik daripada menelusuri list.

Bisakah BFS dua arah membuat Word Ladder lebih cepat?

Ya. Cari dari kedua ujung sekaligus, selalu memperluas sisi yang lebih kecil satu tingkat, lalu berhenti saat kedua sisi bertemu. Dengan sekitar b tetangga untuk setiap kata dan d perubahan, satu pencarian dapat menjangkau sekitar b^d kata; dua pencarian yang bertemu di tengah menjangkau sekitar 2 × b^(d/2).

def ladderLength(beginWord, endWord, wordList):
    # Tulis kodemu di sini

Tes #1

Tes #2

Tes #3

Argumen

beginWord = "lead"
endWord = "gold"
wordList = ["load", "goad", "gold", "lend", "lewd", "bold"]

Output yang diharapkan

Word Ladder

Fungsi

Batasan

Contoh

Petunjuk

Solusi

Coba telusuri setiap tangga dengan pencarian mendalam terlebih dahulu

Pencarian breadth-first, membandingkan setiap pasangan

Pencarian breadth-first dengan bucket wildcard

Jebakan dan kasus tepi

Pertanyaan yang sering diajukan3

Soal serupa