Carian Perkataan II: Trie + Pengunduran pada Grid
Sisipkan semua perkataan sasaran ke dalam trie dan jalankan pengunduran DFS pada papan 2D untuk mencari semua perkataan sah serentak dalam O(m × n × 4^L).
Carian Perkataan II: Trie + Pengunduran pada Grid ialah pelajaran Persediaan Temu Duga Pengaturcaraan percuma di CoddyKit. Ini ialah pelajaran 4 daripada 4. Anda boleh membaca keseluruhan pelajaran di bawah secara percuma — kemudian berlatih secara praktikal dalam pelayar menggunakan penyunting kod terbina dalam dan tutor kecerdasan buatan 24/7. Pelajaran ini merupakan sebahagian daripada laluan pembelajaran Persediaan Temu Duga Pengaturcaraan, dan kemajuan anda disegerakkan merentas web serta aplikasi CoddyKit. Kursus Persediaan Temu Duga Pengaturcaraan merangkumi sejumlah 4 pelajaran.
Masalah Carian Perkataan II
Carian Perkataan II (LeetCode 212): diberikan papan aksara m × n dan senarai perkataan, cari semua perkataan yang boleh dibentuk oleh sel bersebelahan secara berturutan (secara mengufuk atau menegak), dengan setiap sel hanya boleh digunakan sekali. Ini lebih sukar daripada Carian Perkataan I (satu perkataan) kerana kita perlu mencari semua perkataan sepadan secara serentak — menjalankan Carian Perkataan I secara naif bagi setiap perkataan memberikan O(W × m × n × 4^L), yang terlalu perlahan.
Mengapa Pokok Awalan + Penjejakan Balik?
Memasukkan semua perkataan sasaran ke dalam pokok awalan dan kemudian menjalankan penjejakan balik DFS pada papan membolehkan kita mencari semua perkataan secara serentak. Pada setiap sel papan, bukannya memeriksa 'adakah laluan ini membentuk perkataan sasaran saya?', kita memeriksa 'adakah laluan ini sepadan dengan awalan dalam pokok awalan?'. Sebaik sahaja awalan pokok awalan gagal, kita memangkas seluruh cabang DFS — sekali gus mengelakkan kerja berulang merentas semua perkataan yang berkongsi awalan tersebut.
Membina Pokok Awalan daripada Senarai Perkataan
Masukkan semua perkataan ke dalam pokok awalan. Simpan perkataan lengkap pada nod daun dalam node.word, bukannya hanya nilai logik, supaya apabila padanan lengkap ditemui semasa penjejakan balik, kita boleh terus menambah perkataan itu kepada hasil tanpa membinanya semula aksara demi aksara.
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')Penjejakan Balik DFS pada Papan
Mulakan DFS dari setiap sel pada papan. Pada setiap langkah: (1) semak sama ada aksara sel semasa wujud sebagai anak dalam nod pokok awalan semasa; (2) jika ya, tandakan sel itu sebagai telah dilawati (tetapkan kepada penanda seperti '#'), lakukan rekursi ke dalam 4 jiran; (3) selepas rekursi, pulihkan sel itu (buang tanda). Apabila nod pokok awalan mempunyai word yang bukan tiada nilai, tambahkannya kepada hasil dan tetapkan kepada tiada nilai untuk mengelakkan duplicates.
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 Kerumitan
Masa: O(m × n × 4^L), dengan L ialah panjang maksimum perkataan. Bagi setiap satu daripada m×n sel permulaan, DFS menjelajah sehingga 4^L laluan. Pokok awalan memangkas laluan yang tidak sepadan dengan mana-mana awalan perkataan, jadi dalam amalan ia jauh lebih pantas. Membina pokok awalan ialah O(W × L), dengan W ialah bilangan perkataan. Ruang: O(W × L) untuk pokok awalan serta kedalaman timbunan rekursi O(L).
Pemangkasan: Mengalih Keluar Nod Daun Selepas Menemui Perkataan
Selepas menemui sesuatu perkataan, alih keluar nod daun daripada pokok awalan (bukan sekadar menjadikan perkataan itu kosong) jika nod itu tidak mempunyai anak. Ini menghalang cabang yang telah mati daripada dilawati semula dalam panggilan DFS seterusnya. Apabila anak sesuatu nod menjadi kosong selepas perkataan ditemui, alih keluar nod itu daripada kamus anak induknya. Pengoptimuman ini penting apabila banyak perkataan berkongsi 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 Perkataan dalam Nod Lebih Baik
Menyimpan perkataan lengkap pada nod daun pokok awalan (bukannya membinanya semula daripada laluan DFS) mempunyai dua kelebihan: (1) pengambilan perkataan dalam O(1) apabila padanan ditemui, bukannya pembinaan semula laluan dalam O(L); (2) menetapkan node.word = None selepas perkataan ditemui ialah penyahduplikatan O(1) yang kemas tanpa memerlukan set hasil berasingan. Khususnya bagi Carian Perkataan II, pencegahan pendua adalah penting kerana secara teori perkataan yang sama boleh ditemui melalui laluan yang berbeza.
Menandakan Sel yang Dilawati di Tempat
Bukannya menggunakan set visited berasingan (yang memerlukan ruang O(m × n) bagi setiap laluan DFS), kita menandakan sel di tempatnya dengan menggantikan aksaranya menggunakan penanda seperti '#'. Selepas DFS kembali, pulihkan aksara asal. Teknik ini: (1) menggunakan ruang tambahan O(1) bagi setiap sel; (2) secara automatik menghalang lawatan semula dalam satu laluan; (3) telus sepenuhnya kepada penjelajahan pokok awalan kerana '#' tidak akan wujud dalam pokok awalan.
Kes Pinggir yang Perlu Dikendalikan
Kes pinggir penting: (1) perkataan duplicates dalam senarai perkataan — simpan dalam himpunan, atau gunakan helah node.word = None untuk menghalang duplicates dalam hasil; (2) perkataan yang sangat panjang sehingga melebihi dimensi papan — perkataan itu tidak boleh dibentuk, tetapi DFS mengendalikannya secara semula jadi apabila kehabisan sel bersebelahan; (3) papan satu sel — hanya perkataan satu aksara boleh ditemui; (4) perkataan yang sama boleh ditemui melalui laluan berbeza — helah node.word = None menghalang pengiraan dua kali.
Perbandingan dengan Pendekatan Naif
Pendekatan naif: bagi setiap daripada W perkataan, jalankan Carian Perkataan I: O(W × m × n × 4^L). Dengan pokok awalan, semua perkataan dicari secara serentak: O(m × n × 4^L) tanpa mengira W. Bagi W=1000 perkataan dengan panjang 10 pada papan 10×10, pendekatan naif adalah 1000× lebih perlahan daripada pokok awalan. Pokok awalan bertindak sebagai penapis awalan dikongsi yang mengagihkan kos merentas semua perkataan — contoh klasik penggunaan struktur data untuk mencapai peningkatan asimptotik.
Ringkasan Penyelesaian Lengkap
Penyelesaian lengkap Carian Perkataan II: bina pokok awalan dengan perkataan dan simpan rentetan perkataan pada nod daun. Bagi setiap sel papan, jalankan DFS: semak sama ada aksara semasa wujud dalam nod pokok awalan semasa, tandakan sel sebagai '#', lakukan rekursi ke dalam 4 jiran, kemudian pulihkan sel. Apabila word pada nod bukan kosong, tambahkannya kepada hasil dan kosongkan nilainya. Secara pilihan, pangkas cabang pokok awalan yang kosong selepas digunakan. Pulangkan senarai hasil. Masa: O(m×n×4^L), Ruang: pokok awalan 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 resultSemakan Pantas
Uji pemahaman anda tentang konsep Struktur Data & Algoritma — Persediaan Temu Duga Pengekodan daripada pelajaran ini.
Ringkasan Pelajaran
Dalam pelajaran ini anda mempelajari: Carian Perkataan II menggunakan pokok awalan untuk membolehkan search serentak berbilang perkataan dengan pemangkasan awalan dikongsi, menyimpan rentetan perkataan pada daun pokok awalan membolehkan pengambilan perkataan dalam O(1) dan penyahduplikatan mudah dengan menetapkannya kepada tiada nilai selepas ditemui, dan penandaan sel yang dilawati di tempatnya dengan '#' mengelakkan ruang tambahan O(m×n) bagi setiap laluan DFS. Ini melengkapkan kursus Pokok Awalan dan Algoritma Rentetan — anda telah menguasai salah satu struktur data khusus rentetan yang paling berkuasa dan digunakan dalam temu duga.
Pelajari Persediaan Temu Duga Pengaturcaraan dengan tutor kecerdasan buatan — percuma
Tulis dan jalankan kod sebenar dalam pelayar anda, dapatkan bantuan segera daripada tutor kecerdasan buatan yang tersedia 24/7, dan sambung semula dari tempat anda berhenti di web atau dalam aplikasi.
- Kursus
- 90
- Pelajaran
- 360
Soalan Lazim
Adakah pelajaran “Carian Perkataan II: Trie + Pengunduran pada Grid” percuma?
Ya — teks penuh “Carian Perkataan II: Trie + Pengunduran pada Grid” boleh dibaca secara percuma di web ini. Untuk berlatih secara interaktif menggunakan penyunting kod terbina dalam dan tutor kecerdasan buatan 24/7, serta membuka kunci baki kursus Persediaan Temu Duga Pengaturcaraan, tingkat taraf kepada CoddyKit PRO. Kursus Persediaan Temu Duga Pengaturcaraan merangkumi sejumlah 4 pelajaran.
Apakah yang akan saya pelajari dalam “Carian Perkataan II: Trie + Pengunduran pada Grid”?
Sisipkan semua perkataan sasaran ke dalam trie dan jalankan pengunduran DFS pada papan 2D untuk mencari semua perkataan sah serentak dalam O(m × n × 4^L). Anda berlatih Persediaan Temu Duga Pengaturcaraan menggunakan kod praktikal yang dijalankan terus dalam pelayar, manakala tutor kecerdasan buatan 24/7 menjawab soalan anda semasa anda mengikuti pelajaran.
Adakah saya memerlukan pengalaman untuk memulakan Persediaan Temu Duga Pengaturcaraan?
Tiada pengalaman terdahulu diperlukan. Pembelajaran Persediaan Temu Duga Pengaturcaraan di CoddyKit disusun untuk pelajar daripada peringkat pemula hingga lanjutan, jadi anda boleh bermula di sini atau dari awal dan belajar mengikut kadar anda sendiri. Ini ialah pelajaran 4 daripada 4.
Berapa lamakah pelajaran “Carian Perkataan II: Trie + Pengunduran pada Grid” diambil?
Kebanyakan pelajaran CoddyKit mengambil masa kira-kira 5–10 minit. Setiap pelajaran ringkas dan interaktif, jadi anda boleh membuat kemajuan secara berterusan dan menyambung tepat dari tempat anda berhenti di web atau aplikasi.
Bolehkah saya menulis dan menjalankan kod dalam pelajaran Persediaan Temu Duga Pengaturcaraan ini?
Ya. Setiap pelajaran Persediaan Temu Duga Pengaturcaraan menyertakan penyunting kod terbina dalam, jadi anda boleh menulis dan menjalankan kod sebenar terus dalam pelayar serta menerima maklum balas kecerdasan buatan serta-merta — tanpa memerlukan persediaan setempat.
Semua pelajaran dalam kursus ini
- Kelas TrieNode: Sisip dan Cari
- Carian Awalan dan Starts-With
- Carian Kad Bebas dan Regex dalam Trie
- Carian Perkataan II: Trie + Pengunduran pada Grid