Pencarian Kata II: Trie + Penelusuran Mundur pada Grid
Sisipkan semua kata target ke dalam trie dan jalankan DFS dengan penelusuran mundur pada papan 2D untuk menemukan semua kata valid secara bersamaan dalam O(m × n × 4^L)
Pencarian Kata II: Trie + Penelusuran Mundur pada Grid adalah pelajaran DSA Interview Prep gratis di CoddyKit. Ini adalah pelajaran 4 dari 4. Kamu bisa membaca pelajaran lengkapnya di bawah secara gratis — lalu praktikkan langsung di browser dengan editor kode bawaan dan tutor AI 24/7. Ini adalah bagian dari jalur belajar DSA Interview Prep, dan progresmu tersinkronisasi di web dan aplikasi CoddyKit. Kursus DSA Interview Prep mencakup 4 pelajaran total.
Masalah Pencarian Kata II
Pencarian Kata II (LeetCode 212): diberikan papan karakter berukuran m × n dan daftar kata, temukan semua kata yang dapat dibentuk oleh sel-sel yang bersebelahan secara berurutan (secara horizontal atau vertikal), dengan setiap sel hanya boleh digunakan sekali. Ini lebih sulit daripada Pencarian Kata I (satu kata) karena kita perlu menemukan semua kata yang cocok secara bersamaan — menjalankan Pencarian Kata I secara naif untuk setiap kata memiliki kompleksitas O(W × m × n × 4^L), yang terlalu lambat.
Mengapa Trie + Pelacakan Mundur?
Memasukkan semua kata target ke dalam trie lalu menjalankan pelacakan mundur DFS pada papan memungkinkan kita mencari semua kata secara bersamaan. Pada setiap sel papan, alih-alih memeriksa “apakah jalur ini membentuk kata target saya?”, kita memeriksa “apakah jalur ini cocok dengan suatu awalan dalam trie?”. Begitu suatu awalan trie tidak cocok, kita memangkas seluruh cabang DFS tersebut — sehingga pekerjaan berulang untuk semua kata yang berbagi awalan dapat dihindari.
Membangun Trie dari Daftar Kata
Sisipkan semua kata ke dalam trie. Simpan kata lengkap pada simpul daun (dalam node.word), bukan hanya nilai benar-salah, sehingga ketika kecocokan lengkap ditemukan selama pelacakan mundur, kita dapat langsung menambahkan kata tersebut ke hasil tanpa menyusunnya kembali karakter demi karakter.
class TrieNode:
def __init__(self):
self.children = {}
self.word = None # stores the complete word if this is an end node
def build_trie(words):
root = TrieNode()
for word in words:
node = root
for c in word:
if c not in node.children:
node.children[c] = TrieNode()
node = node.children[c]
node.word = word # mark complete word here
return root
root = build_trie(['eat','oath','ot'])
print('Trie built with', len(root.children), 'root children')Pelacakan Mundur DFS pada Kisi
Mulai DFS dari setiap sel pada papan. Pada setiap langkah: (1) periksa apakah karakter sel saat ini tersedia sebagai anak pada simpul trie saat ini; (2) jika ya, tandai sel sebagai telah dikunjungi (ubah menjadi penanda seperti '#'), lalu lakukan rekursi ke 4 tetangga; (3) setelah rekursi selesai, pulihkan sel tersebut (hapus tandanya). Saat simpul trie memiliki word yang bukan null, tambahkan kata tersebut ke hasil dan ubah nilainya menjadi null untuk mencegah duplikat.
class TrieNode:
def __init__(self):
self.children = {}
self.word = None
def findWords(board, words):
root = TrieNode()
for word in words:
node = root
for c in word:
if c not in node.children:
node.children[c] = TrieNode()
node = node.children[c]
node.word = word
m, n = len(board), len(board[0])
result = []
def dfs(i, j, node):
c = board[i][j]
if c not in node.children:
return
next_node = node.children[c]
if next_node.word:
result.append(next_node.word)
next_node.word = None # avoid duplicates
board[i][j] = '#' # mark visited
for di, dj in [(-1,0),(1,0),(0,-1),(0,1)]:
ni, nj = i+di, j+dj
if 0<=ni<m and 0<=nj<n and board[ni][nj] != '#':
dfs(ni, nj, next_node)
board[i][j] = c # restore
for i in range(m):
for j in range(n):
dfs(i, j, root)
return result
board = [['o','a','a','n'],['e','t','a','e'],['i','h','k','r'],['i','f','l','v']]
words = ['oath','pea','eat','rain']
print(findWords(board, words)) # ['oath','eat']Analisis Kompleksitas
Waktu: O(m × n × 4^L), dengan L sebagai panjang kata maksimum. Untuk setiap sel awal berjumlah m×n, DFS menelusuri hingga 4^L jalur. Trie memangkas jalur yang tidak cocok dengan awalan kata mana pun, sehingga dalam praktiknya proses ini jauh lebih cepat. Membangun trie memiliki kompleksitas O(W × L), dengan W sebagai jumlah kata. Ruang: O(W × L) untuk trie ditambah kedalaman tumpukan rekursi O(L).
Pemangkasan: Menghapus Simpul Daun Setelah Menemukan Kata
Setelah menemukan sebuah kata, hapus simpul daun dari trie (bukan hanya mengosongkan kata) jika simpul tersebut tidak memiliki anak. Hal ini mencegah penelusuran kembali ke cabang mati dalam pemanggilan DFS berikutnya. Saat anak-anak suatu simpul menjadi kosong setelah kata ditemukan, hapus simpul tersebut dari kamus anak milik induknya. Optimasi ini sangat berarti ketika banyak kata berbagi awalan yang panjang.
def dfs_with_pruning(i, j, node, board, m, n, result):
c = board[i][j]
if c not in node.children:
return
next_node = node.children[c]
if next_node.word:
result.append(next_node.word)
next_node.word = None
board[i][j] = '#'
for di, dj in [(-1,0),(1,0),(0,-1),(0,1)]:
ni, nj = i+di, j+dj
if 0<=ni<m and 0<=nj<n and board[ni][nj] != '#':
dfs_with_pruning(ni, nj, next_node, board, m, n, result)
board[i][j] = c
# Prune: if the node has no more children and no word, remove it
if not next_node.children and not next_node.word:
del node.children[c]
print('Leaf pruning removes exhausted trie branches during search')Mengapa Menyimpan word di Simpul Lebih Baik
Menyimpan kata lengkap pada simpul daun trie (alih-alih menyusunnya kembali dari jalur DFS) memiliki dua keuntungan: (1) pengambilan kata dalam O(1) saat kecocokan ditemukan, bukan rekonstruksi jalur dalam O(L); (2) menetapkan node.word = None setelah kata ditemukan merupakan deduplikasi O(1) yang rapi tanpa memerlukan himpunan hasil terpisah. Khususnya untuk Pencarian Kata II, pencegahan duplikat penting karena secara teori kata yang sama dapat ditemukan melalui jalur yang berbeda.
Menandai Sel yang Dikunjungi Secara Langsung
Alih-alih menggunakan himpunan visited terpisah (yang memerlukan ruang O(m × n) untuk setiap jalur DFS), tandai sel secara langsung dengan mengganti karakternya menggunakan penanda seperti '#'. Setelah DFS selesai, pulihkan karakter aslinya. Teknik ini: (1) menggunakan ruang tambahan O(1) per sel; (2) secara otomatis mencegah kunjungan ulang dalam satu jalur; (3) sepenuhnya transparan bagi penelusuran trie karena '#' tidak akan pernah ada dalam trie.
Kasus Khusus yang Perlu Ditangani
Kasus khusus yang penting: (1) kata duplikat dalam daftar kata — simpan dalam himpunan, atau gunakan trik node.word = None untuk mencegah duplikat pada hasil; (2) kata yang sangat panjang dan melebihi dimensi papan — kata tersebut tidak dapat dibentuk, tetapi DFS secara alami menanganinya ketika kehabisan sel yang bersebelahan; (3) papan satu sel — hanya kata yang terdiri dari satu karakter yang dapat ditemukan; (4) kata yang sama dapat ditemukan melalui jalur berbeda — trik node.word = None mencegah penghitungan ganda.
Perbandingan dengan Pendekatan Naif
Pendekatan naif: untuk setiap dari W kata, jalankan Pencarian Kata I: O(W × m × n × 4^L). Dengan trie, semua kata dicari secara bersamaan: O(m × n × 4^L), terlepas dari W. Untuk W=1000 kata dengan panjang 10 pada papan berukuran 10×10, pendekatan naif 1000× lebih lambat daripada trie. Trie bertindak sebagai penyaring awalan bersama yang membagi biaya di antara semua kata — contoh klasik penggunaan struktur data untuk mencapai peningkatan asimtotik.
Ringkasan Solusi Lengkap
Solusi lengkap Pencarian Kata II: bangun trie dengan kata-kata dan simpan teks kata pada simpul daun. Untuk setiap sel papan, jalankan DFS: periksa apakah karakter saat ini tersedia pada simpul trie saat ini, tandai sel sebagai '#', lakukan rekursi ke 4 tetangga, lalu pulihkan sel. Saat node.word bukan null, tambahkan kata tersebut ke hasil dan kosongkan nilainya. Anda juga dapat memangkas cabang trie yang kosong setelah digunakan. Kembalikan daftar hasil. Waktu: O(m×n×4^L), Ruang: trie O(W×L) + rekursi O(L).
class TrieNode:
def __init__(self):
self.children = {}
self.word = None
def findWords_final(board, words):
root = TrieNode()
for word in words:
node = root
for c in word:
node = node.children.setdefault(c, TrieNode())
node.word = word
m, n = len(board), len(board[0])
result = []
def dfs(i, j, node):
c = board[i][j]
child = node.children.get(c)
if not child:
return
if child.word:
result.append(child.word)
child.word = None
board[i][j] = '#'
for di, dj in [(-1,0),(1,0),(0,-1),(0,1)]:
ni, nj = i+di, j+dj
if 0<=ni<m and 0<=nj<n and board[ni][nj] != '#':
dfs(ni, nj, child)
board[i][j] = c
if not child.children:
del node.children[c]
for i in range(m):
for j in range(n):
dfs(i, j, root)
return resultPemeriksaan Singkat
Uji pemahaman Anda tentang konsep Struktur Data & Algoritma — Persiapan Wawancara Pemrograman dari pelajaran ini.
Ringkasan Pelajaran
Dalam pelajaran ini Anda telah mempelajari: Pencarian Kata II menggunakan trie untuk memungkinkan pencarian banyak kata secara bersamaan dengan pemangkasan awalan bersama, menyimpan teks kata pada simpul daun trie memungkinkan pengambilan kata O(1) dan deduplikasi mudah dengan mengubahnya menjadi None setelah ditemukan, dan penandaan sel yang telah dikunjungi secara langsung menggunakan '#' menghindari ruang tambahan O(m×n) untuk setiap jalur DFS. Ini menyelesaikan kursus Trie dan Algoritma Teks — Anda telah menguasai salah satu struktur data khusus teks yang paling kuat dan sering digunakan dalam wawancara.
Pertanyaan yang Sering Diajukan
Apakah pelajaran “Pencarian Kata II: Trie + Penelusuran Mundur pada Grid” gratis?
Ya — teks lengkap “Pencarian Kata II: Trie + Penelusuran Mundur pada Grid” gratis dibaca di sini di web. Untuk praktiknya secara interaktif (editor kode bawaan dan tutor AI 24/7) dan buka sisa kursus DSA Interview Prep, upgrade ke CoddyKit PRO. Kursus DSA Interview Prep mencakup 4 pelajaran total.
Apa yang akan aku pelajari di “Pencarian Kata II: Trie + Penelusuran Mundur pada Grid”?
Sisipkan semua kata target ke dalam trie dan jalankan DFS dengan penelusuran mundur pada papan 2D untuk menemukan semua kata valid secara bersamaan dalam O(m × n × 4^L) Kamu berlatih DSA Interview Prep dengan kode praktik yang langsung kamu jalankan di browser, dan tutor AI 24/7 menjawab pertanyaanmu saat kamu mengerjakan pelajaran ini.
Apakah aku perlu pengalaman untuk memulai DSA Interview Prep?
Tidak diperlukan pengalaman sebelumnya. DSA Interview Prep di CoddyKit dirancang untuk pemula hingga pelajar tingkat lanjut, jadi kamu bisa memulai di sini atau dari awal dan belajar sesuai kecepatan kamu sendiri. Ini adalah pelajaran 4 dari 4.
Berapa lama pelajaran “Pencarian Kata II: Trie + Penelusuran Mundur pada Grid” memakan waktu?
Sebagian besar pelajaran CoddyKit memakan waktu sekitar 5–10 menit. Setiap pelajaran ringkas dan interaktif, jadi kamu membuat kemajuan stabil dan melanjutkan dari tempat kamu tinggalkan di web dan aplikasi.
Bisakah aku menulis dan menjalankan kode dalam pelajaran DSA Interview Prep ini?
Ya. Setiap pelajaran DSA Interview Prep menyertakan editor kode bawaan, jadi kamu menulis dan menjalankan kode nyata langsung di browser dan mendapatkan umpan balik AI instan — tidak diperlukan penyiapan lokal.
Semua pelajaran dalam kursus ini
- Class TrieNode: Penyisipan dan Pencarian
- Pencarian Awalan dan Starts-With
- Pencarian Wildcard dan Regex dalam Trie
- Pencarian Kata II: Trie + Penelusuran Mundur pada Grid