Word Search

Q: Berapa kompleksitas waktu Word Search?

O(m·n·3^L) untuk papan berukuran m × n dan kata dengan panjang L : setiap sel dapat menjadi awal jalur, dan setelah langkah pertama, setiap sel memiliki paling banyak tiga tetangga yang belum dikunjungi. Ruang tambahan sebesar O(L) untuk rekursi, ditambah O(m·n) untuk salinan papan.

SedangBacktracking Graf

+10

Kamu mendapatkan grid huruf board, sebuah list string dengan board[r][c] sebagai huruf pada baris r, kolom c, dan sebuah string word.

Kembalikan true jika kamu bisa menelusuri word: mulai dari sel mana pun dan setiap langkah pindah ke sel di atas, di bawah, di kiri, atau di kanan, sehingga sel yang kamu kunjungi membentuk word secara berurutan, tanpa menggunakan sel yang sama dua kali. Jika tidak, kembalikan false. Huruf peka terhadap kapitalisasi.

Fungsi

exist(board: string-array, word: string) → boolean

boardstring-array: grid, satu string huruf untuk setiap baris
wordstring: kata yang akan ditelusuri
Mengembalikanboolean: apakah kata dapat ditelusuri melalui sel-sel yang berdampingan, dengan setiap sel digunakan paling banyak satu kali

Batasan

1 ≤ board.length ≤ 6
1 ≤ board[i].length ≤ 6, dan setiap baris memiliki panjang yang sama.
1 ≤ word.length ≤ 20
board dan word hanya berisi huruf bahasa Inggris, huruf besar dan huruf kecil.

Contoh

Input: board = ["STAR", "POOL", "ENDS"]word = "STOOLS"
Output: true
Penjelasan: Mulai dari S di kiri atas, bergerak ke kanan menuju T, turun ke O, bergerak ke kanan menuju O dan L, lalu turun ke S di bawah L. Tidak ada sel yang berulang.

Input: board = ["STAR", "POOL", "ENDS"]word = "POP"
Output: false
Penjelasan: Papan memiliki satu P. Setelah P dan O, kamu memerlukan P lagi, tetapi satu-satunya P yang ada adalah sel awal, yang tidak dapat digunakan dua kali.

Input: board = ["STAR", "POOL", "ENDS"]word = "SAND"
Output: false
Penjelasan: Setiap huruf dari SAND ada di papan, tetapi satu-satunya A, di baris 0, kolom 2, tidak bersentuhan dengan S.

Pertanyaan lanjutan

Daripada menjawab ya atau tidak, bisakah kamu menghitung berapa banyak penelusuran berbeda untuk word yang ada di papan?

Petunjuk

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

0 dari 3 dibuka

Solusi

Kamu harus mencari jalur-jalur melalui kisi. Backtracking membangun satu jalur dengan menambahkan satu huruf setiap kali, menandai setiap sel selama jalur melewatinya dan menghapus tandanya saat kembali, sehingga tidak ada jalur yang menggunakan ulang sel. Pencarian ini memiliki kompleksitas eksponensial terhadap panjang kata, yang masih memungkinkan pada papan berukuran 6 × 6.

Backtracking dengan grid yang telah dikunjungi

Intuisi

Path yang membentuk huruf pertama i akan berlanjut ke tetangga mana pun yang berisi word[i] dan belum ada di path. Jika tidak ada tetangga seperti itu, path tersebut buntu dan kamu mundur.

Menghapus tanda inilah yang membuat cara ini benar: sel yang dilewati path buntu harus tersedia untuk percobaan berikutnya. Pada AA / AB dengan AAA, kedua percobaan dari kiri atas buntu. Jika sel-selnya tetap ditandai, jawabannya, kiri bawah lalu kiri atas lalu kanan atas, akan terlewat.

Setelah langkah pertama, setiap langkah memiliki paling banyak tiga arah baru, sehingga pencarian dapat menjelajahi hingga m·n·3^L path. Pada papan berukuran 5 × 5 yang berisi A, dengan 8 A lalu satu B, pencarian memeriksa sekitar 53.000 sel sebelum menjawab false.

Algoritma

Buat grid visited, semuanya bernilai false.
dfs(r, c, i): false jika (r, c) berada di luar grid, sudah dikunjungi, atau bukan word[i]; true jika i adalah indeks terakhir.
Jika tidak, tandai (r, c), coba empat tetangganya dengan i+1, hapus tandanya, lalu kembalikan apakah ada yang berhasil.
Kembalikan true jika dfs(r, c, 0) berhasil dari sel mana pun.

def exist(board, word):
    rows, cols = len(board), len(board[0])
    visited = [[False] * cols for _ in range(rows)]

    def dfs(r, c, i):
        # Can word[i:] be traced starting at cell (r, c)?
        if r < 0 or r >= rows or c < 0 or c >= cols:
            return False
        if visited[r][c] or board[r][c] != word[i]:
            return False
        if i == len(word) - 1:
            return True
        visited[r][c] = True   # mark: the current path owns this cell
        found = (dfs(r + 1, c, i + 1) or dfs(r - 1, c, i + 1)
                 or dfs(r, c + 1, i + 1) or dfs(r, c - 1, i + 1))
        visited[r][c] = False  # restore: other paths may use it
        return found

    for r in range(rows):
        for c in range(cols):
            if dfs(r, c, 0):
                return True
    return False

Backtracking dengan penanda di tempat dan pemangkasan

Intuisi

Lanjutkan pencarian, dengan dua perubahan. Tandai sel pada salinan papan dengan menulis #, lalu pulihkan hurufnya saat kembali. # tidak pernah cocok dengan huruf dalam kata, jadi pemeriksaan huruf juga menolak sel yang berada di jalur.

Lalu lakukan pemangkasan. Jika kata membutuhkan lebih banyak huruf tertentu daripada yang tersedia di papan, kembalikan false: cara ini menjawab kasus papan yang hanya berisi A tanpa pencarian. Jalur yang dibaca dari belakang mengeja kata yang dibalik pada sel yang sama, jadi pencarian kata yang dibalik memberikan jawaban yang sama. Mulai dari ujung yang hurufnya lebih jarang di papan: lebih sedikit sel yang bisa menjadi titik awal, dan titik awal yang salah langsung gagal.

Dengan satu-satunya B berada di sudut di antara dua C, pencarian maju melakukan sekitar 35.000 pemeriksaan sel; jika dibalik, 27. Kasus terburuk tetap O(m·n·3^L).

Algoritma

Jika kata membutuhkan lebih banyak salinan huruf tertentu daripada yang tersedia di papan, kembalikan false.
Jika papan memiliki lebih banyak salinan word[0] daripada huruf terakhir, balik urutan word.
Salin papan ke dalam kisi yang bisa kamu ubah.
dfs(r, c, i): gagal jika sel bukan word[i]; berhasil jika berada di indeks terakhir; jika tidak, ubah nilainya menjadi #, coba setiap tetangga dalam batas dengan i+1, pulihkan nilainya, lalu kembalikan apakah ada percobaan yang berhasil.
Kembalikan true jika dfs berhasil dari sel mana pun.

from collections import Counter


def exist(board, word):
    rows, cols = len(board), len(board[0])

    # Pruning 1: the board must hold every letter as many times as the word uses it.
    have = Counter("".join(board))
    for letter, need in Counter(word).items():
        if have[letter] < need:
            return False

    # Pruning 2: a path read backwards is the same path, so start from the
    # end whose letter is rarer on the board: fewer cells begin a search.
    if have[word[0]] > have[word[-1]]:
        word = word[::-1]

    grid = [list(row) for row in board]

    def dfs(r, c, i):
        # Can word[i:] be traced starting at cell (r, c)?
        if grid[r][c] != word[i]:
            return False
        if i == len(word) - 1:
            return True
        grid[r][c] = "#"  # mark: "#" matches no letter, so this path cannot reuse the cell
        found = False
        for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
            if 0 <= nr < rows and 0 <= nc < cols and dfs(nr, nc, i + 1):
                found = True
                break
        grid[r][c] = word[i]  # restore the letter for other paths
        return found

    for r in range(rows):
        for c in range(cols):
            if dfs(r, c, 0):
                return True
    return False

Jebakan dan kasus tepi

Tidak menghapus tanda dari sel setelah cabang gagal: AAA pada AA / AB menghasilkan false.
Sama sekali tidak memberi tanda: jalur kembali ke sel terakhirnya, dan POP pada papan contoh menghasilkan true.
Membaca sel sebelum memeriksa batas: di Python, board[-1] adalah baris terakhir, sehingga jalur berputar kembali ke sisi lain grid.
Memeriksa keberhasilan hanya setelah bergerak: ["A"] dengan A harus menghasilkan true.
Memberi tanda dengan menukar huruf besar-kecil pada sel: pada ["aA"], a yang diberi tanda terbaca sebagai A kedua, sehingga aAA menghasilkan true.

Pertanyaan yang sering diajukan3

Berapa kompleksitas waktu Word Search?

O(m·n·3^L) untuk papan berukuran m × n dan kata dengan panjang L: setiap sel dapat menjadi awal jalur, dan setelah langkah pertama, setiap sel memiliki paling banyak tiga tetangga yang belum dikunjungi. Ruang tambahan sebesar O(L) untuk rekursi, ditambah O(m·n) untuk salinan papan.

Bagaimana pemangkasan membuat Word Search lebih cepat?

Hitung huruf terlebih dahulu, lalu kembalikan false jika papan berisi terlalu sedikit salah satu huruf. Kemudian, mulailah pencarian dari ujung dengan huruf yang lebih jarang, yang dapat menjadi awal dari lebih sedikit sel. Kedua pemeriksaan ini tidak mengubah kasus terburuk.

Apa perbedaan antara Word Search dan Word Search II?

Word Search II menanyakan kata mana dari sebuah list yang muncul di papan. Mencari sekali untuk setiap kata mengulang pekerjaan, jadi solusi yang umum adalah menyimpan kata-kata dalam trie dan menelusuri papan sekali, lalu menghentikan penelusuran saat tidak ada kata yang dimulai dengan huruf-hurufnya.

def exist(board, word):
    # Tulis kodemu di sini

Tes #1

Tes #2

Tes #3

Argumen

board = ["STAR", "POOL", "ENDS"]
word = "STOOLS"

Output yang diharapkan

true