Pencarian Wildcard dan Regex dalam Trie
Dukung pencocokan wildcard '.' dengan menyebar ke semua anak pada kedalaman tersebut, sehingga dapat menyelesaikan masalah struktur data design-add-and-search-words
Pencarian Wildcard dan Regex dalam Trie adalah pelajaran DSA Interview Prep gratis di CoddyKit. Ini adalah pelajaran 3 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 dengan Karakter Pengganti
Pencarian pada trie standar menangani karakter yang tepat. Pencarian dengan karakter pengganti menambahkan karakter khusus '.' yang cocok dengan satu karakter apa pun. Saat menemukan '.' selama pencarian, alih-alih mengikuti satu anak tertentu, kita harus mencoba semua anak — sebuah percabangan. Inilah gagasan utama di balik LeetCode 211, “Merancang Struktur Data untuk Menambahkan dan Mencari Kata”. Setiap '.' menggandakan jalur pencarian berdasarkan jumlah anak pada tingkat tersebut.
Pencarian Rekursif dengan Karakter Pengganti
Terapkan pencarian dengan karakter pengganti menggunakan pembantu DFS rekursif. Untuk setiap karakter dalam pola: jika karakter tersebut merupakan karakter harfiah, ikuti anak tertentu (atau kembalikan nilai salah jika tidak ada); jika karakter tersebut adalah '.', lakukan rekursi ke semua anak dan kembalikan nilai benar jika salah satunya berhasil. Di akhir pola, kembalikan node.is_end.
class TrieNode:
def __init__(self):
self.children = {}
self.is_end = False
class WordDictionary:
def __init__(self):
self.root = TrieNode()
def addWord(self, word):
node = self.root
for c in word:
if c not in node.children:
node.children[c] = TrieNode()
node = node.children[c]
node.is_end = True
def search(self, word):
def dfs(node, i):
if i == len(word):
return node.is_end
c = word[i]
if c == '.':
return any(dfs(child, i+1) for child in node.children.values())
if c not in node.children:
return False
return dfs(node.children[c], i+1)
return dfs(self.root, 0)
wd = WordDictionary()
wd.addWord('bad')
wd.addWord('dad')
wd.addWord('mad')
print(wd.search('.ad')) # True
print(wd.search('b..')) # True
print(wd.search('pad')) # FalseMengapa Percabangan Dapat Berhenti Lebih Awal
Saat menemukan '.', kita memanggil any(dfs(child, i+1) for child in node.children.values()). Generator any() menggunakan evaluasi berhenti lebih awal — generator tersebut berhenti segera setelah salah satu anak menghasilkan nilai benar. Hal ini menghindari penelusuran yang tidak perlu. Dalam kasus terburuk (pola yang seluruhnya terdiri dari '.'), kita menelusuri semua jalur — kompleksitasnya adalah O(26^k), dengan k sebagai jumlah titik, sehingga pola seperti '....' mahal untuk trie berukuran besar.
Pencarian Karakter Pengganti Iteratif dengan Antrean
Pendekatan iteratif menggunakan antrean yang berisi pasangan (node, index). Mulailah dengan (root, 0). Untuk setiap pasangan, jika index == len(word) dan node.is_end, kembalikan nilai benar. Jika tidak, proses karakter saat ini: untuk '.', masukkan semua anak ke antrean; untuk karakter harfiah, masukkan hanya anak yang cocok. Ini pada dasarnya adalah BFS pada jalur-jalur trie.
from collections import deque
def search_iterative(root, word):
queue = deque([(root, 0)])
while queue:
node, i = queue.popleft()
if i == len(word):
if node.is_end:
return True
continue
c = word[i]
if c == '.':
for child in node.children.values():
queue.append((child, i+1))
elif c in node.children:
queue.append((node.children[c], i+1))
return False
print('Iterative BFS-based wildcard search')Analisis Kompleksitas Pencarian dengan Karakter Pengganti
Untuk pola tanpa karakter pengganti, pencarian memiliki kompleksitas O(m). Untuk pola dengan k karakter pengganti, kasus terburuknya adalah O(26^k × m) — eksponensial terhadap jumlah karakter pengganti. Dalam praktiknya, karakter pengganti biasanya jarang digunakan dan trie tidak dalam, sehingga kinerjanya dapat diterima. Untuk pola yang seluruhnya terdiri dari karakter pengganti (misalnya, mencocokkan semua kata dengan panjang k), prosesnya berubah menjadi penelusuran trie secara menyeluruh.
Pencarian Ekspresi Reguler di Luar Karakter Pengganti Tunggal
Perluasan ke ekspresi reguler lengkap (misalnya, '*' yang mencocokkan nol atau lebih karakter) memerlukan penanganan yang berbeda. Sebuah '*' dapat mencocokkan akhiran apa pun, sehingga saat menemukannya, kita harus mencoba semua jalur trie dari simpul saat ini. Pencocokan ekspresi reguler yang sebenarnya pada trie bersifat kompleks — biasanya digunakan untuk konstruksi NFA/DFA. Dalam wawancara, karakter pengganti tunggal ('.') adalah pola standar.
Pencocokan Pola Glob
Pencocokan glob dengan '?' (karakter tunggal apa pun) dan '*' (urutan apa pun, termasuk urutan kosong) dapat diterapkan dengan DP. Jika diterapkan pada trie, '?' memetakan ke percabangan satu tingkat (seperti '.') dan '*' memetakan ke DFS bertingkat. Pendekatan DP gabungan: dp[i][j] = benar jika pattern[0..i] cocok dengan string[0..j]. Pewawancara biasanya menentukan varian mana yang harus diterapkan.
Penerapan Praktis: Perutean Alamat IP
Trie dengan karakter pengganti digunakan dalam tabel perutean IP, dengan '*' yang berfungsi sebagai karakter pengganti awalan. Router menyimpan awalan rute seperti '192.168.*' dan mencocokkannya dengan alamat yang masuk. Pencocokan awalan terpanjang (rute yang paling spesifik menjadi pemenang) diterapkan dengan menelusuri trie sedalam mungkin dan menggunakan kecocokan terakhir yang ditemukan. Ini adalah penerapan nyata dari operasi awalan dan karakter pengganti pada trie.
Optimasi: Memangkas Cabang Mati
Saat simpul trie tidak memiliki anak (simpul daun) dan is_end = False, pencarian apa pun yang mencapai simpul tersebut akan menghasilkan nilai salah. Selama pencarian dengan karakter pengganti, melewati simpul buntu ini sebelum melakukan rekursi dapat memangkas pemanggilan yang tidak perlu. Mempertahankan jumlah kata pada setiap simpul (total kata dalam subpohon) memungkinkan kita melewati seluruh subpohon jika tidak ada kata yang cocok dengan batasan panjang pola yang tersisa.
Kelas WordDictionary Lengkap (Siap untuk Wawancara)
WordDictionary yang rapi dan siap digunakan dalam wawancara, yang menggabungkan penyisipan dan pencarian dengan karakter pengganti titik dalam satu kelas. Inilah penerapan yang diharapkan untuk LeetCode 211. Pencarian rekursif dengan fungsi any() yang berhenti lebih awal bersifat ringkas dan menunjukkan logika percabangan dengan jelas kepada pewawancara.
class WordDictionary:
def __init__(self):
self.root = {}
def addWord(self, word):
node = self.root
for c in word:
node = node.setdefault(c, {})
node['#'] = True
def search(self, word):
def dfs(node, i):
if i == len(word):
return '#' in node
if word[i] == '.':
return any(dfs(v, i+1) for k, v in node.items() if k != '#')
nxt = node.get(word[i])
return dfs(nxt, i+1) if nxt is not None else False
return dfs(self.root, 0)
wd = WordDictionary()
for w in ['at','and','an','add']:
wd.addWord(w)
print(wd.search('a.')) # True (at, an)
print(wd.search('.nd')) # True (and)
print(wd.search('...')) # True (and, add)
print(wd.search('x.')) # FalseMenggunakan setdefault untuk Trie Ringkas
dict.setdefault(key, default) mengembalikan nilai untuk key jika tersedia; jika tidak, fungsi tersebut menyisipkan default lalu mengembalikannya. Menggunakan node.setdefault(c, {}) dalam penyisipan menghilangkan pemeriksaan kondisi: fungsi tersebut membuat kamus anak jika belum ada dan mengembalikannya dalam kedua keadaan. Hal ini membuat penyisipan menjadi penelusuran satu baris: for c in word: node = node.setdefault(c, {}). Rapi dan sesuai gaya Python.
Pemeriksaan Singkat
Uji pemahaman Anda tentang konsep Struktur Data & Algoritma — Persiapan Wawancara Pemrograman dari pelajaran ini.
Ringkasan Pelajaran
Dalam pelajaran ini Anda telah mempelajari: karakter pengganti '.' memerlukan percabangan ke semua anak pada posisi yang cocok menggunakan DFS rekursif, penggunaan generator untuk evaluasi apa pun menyediakan evaluasi berhenti lebih awal demi penghentian dini, dan setdefault memungkinkan penyisipan trie ringkas dalam satu baris. Selanjutnya, kita akan menggabungkan trie dan pelacakan mundur untuk menyelesaikan Pencarian Kata II — menemukan banyak kata secara bersamaan pada papan 2D.
Pertanyaan yang Sering Diajukan
Apakah pelajaran “Pencarian Wildcard dan Regex dalam Trie” gratis?
Ya — teks lengkap “Pencarian Wildcard dan Regex dalam Trie” 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 Wildcard dan Regex dalam Trie”?
Dukung pencocokan wildcard '.' dengan menyebar ke semua anak pada kedalaman tersebut, sehingga dapat menyelesaikan masalah struktur data design-add-and-search-words 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 3 dari 4.
Berapa lama pelajaran “Pencarian Wildcard dan Regex dalam Trie” 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