Pencarian Awalan dan Starts-With
Tambahkan metode starts_with yang mengembalikan true jika ada kata yang disisipkan dan memiliki awalan tertentu yang sama, lalu gunakan untuk mengimplementasikan saran pelengkapan otomatis
Pencarian Awalan dan Starts-With adalah pelajaran Coding Interview Prep gratis di CoddyKit. Ini adalah pelajaran 2 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 Coding Interview Prep, dan progresmu tersinkronisasi di web dan aplikasi CoddyKit. Kursus Coding Interview Prep mencakup 4 pelajaran total.
Kekuatan Kueri Prefiks
Keunggulan utama Trie dibandingkan peta hash adalah kueri prefiks yang efisien. Kueri prefiks menjawab: 'berapa banyak kata tersimpan yang dimulai dengan prefiks ini?', 'apa saja kata tersimpan dengan prefiks ini?', atau cukup 'apakah ada kata yang diawali prefiks ini?'. Kueri ini berkompleksitas O(p), dengan p sebagai panjang prefiks, terlepas dari jumlah total kata yang disimpan — sehingga Trie ideal untuk autocomplete dan saran pencarian.
Metode starts_with
starts_with(prefix) mengembalikan nilai benar jika ada kata tersimpan yang diawali prefiks yang diberikan. Telusuri Trie dengan mengikuti setiap karakter prefiks. Jika semua karakter dapat diikuti tanpa menemukan sisi yang hilang, prefiks tersebut ada dan setidaknya satu kata diawali prefiks itu. Implementasinya identik dengan search, kecuali kita mengembalikan nilai benar segera setelah penelusuran selesai — kita tidak memeriksa is_end.
class TrieNode:
def __init__(self):
self.children = {}
self.is_end = False
class Trie:
def __init__(self):
self.root = TrieNode()
def insert(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 starts_with(self, prefix):
node = self.root
for c in prefix:
if c not in node.children:
return False
node = node.children[c]
return True
t = Trie()
for w in ['hello','help','world','word']:
t.insert(w)
print(t.starts_with('hel')) # True
print(t.starts_with('wor')) # True
print(t.starts_with('xyz')) # Falseautocomplete: Menemukan Semua Kata dengan Prefiks
Untuk mengimplementasikan autocomplete, telusuri hingga simpul akhir prefiks, lalu lakukan DFS (atau BFS) dari simpul tersebut untuk mengumpulkan semua kata yang bercabang darinya. Tambahkan prefiks di awal setiap sufiks yang terkumpul untuk membentuk kembali kata lengkap. Operasi ini berkompleksitas O(p + W), dengan W sebagai jumlah total karakter dalam semua kata yang cocok.
class TrieNode:
def __init__(self):
self.children = {}
self.is_end = False
class Trie:
def __init__(self):
self.root = TrieNode()
def insert(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 autocomplete(self, prefix):
node = self.root
for c in prefix:
if c not in node.children:
return []
node = node.children[c]
# DFS from prefix end node
results = []
def dfs(n, path):
if n.is_end:
results.append(prefix + path)
for char, child in n.children.items():
dfs(child, path + char)
dfs(node, '')
return results
t = Trie()
for w in ['apple','app','application','apply','apt']:
t.insert(w)
print(t.autocomplete('app')) # ['app','apple','apply','application']Mengembalikan Saran Terurut
Untuk autocomplete terurut, telusuri anak dalam urutan alfabet selama DFS (lakukan iterasi pada sorted(node.children.items())). Karena anak disimpan dalam kamus, hal ini menambah beban tambahan O(ukuran ALPHABET × kedalaman), tetapi menjamin hasil dalam urutan leksikografis. Trie berbasis larik selalu mengiterasikan anak dalam urutan alfabet karena indeks 0–25 sudah berurutan.
def dfs_sorted(node, prefix, results):
if node.is_end:
results.append(prefix)
for char in sorted(node.children.keys()): # alphabetical order
dfs_sorted(node.children[char], prefix + char, results)
print('Iterating children in sorted order gives lex-sorted suggestions')Saran autocomplete K Teratas
Untuk saran K teratas berdasarkan frekuensi, tambahkan penghitung pada setiap simpul yang mencatat berapa kali kata yang berakhir di sana telah dicari. Saat mengumpulkan saran, gunakan tumpukan maksimum berukuran k. Hal ini mengurangi himpunan hasil DFS berukuran O(W) menjadi O(k) tanpa membuat semua kecocokan secara eksplisit. Mesin pencari dunia nyata menggabungkan penelusuran prefiks Trie dengan data frekuensi untuk menghasilkan saran yang cepat dan relevan.
Implementasi Trie untuk LeetCode 208
LeetCode 208 “Implementasikan Trie (Pohon Prefiks)” meminta tepat: insert(word), search(word) yang mengembalikan nilai logika untuk kecocokan persis, dan startsWith(prefix) yang mengembalikan nilai logika untuk kecocokan prefiks. Ini adalah implementasi Trie standar. Ingat: search memerlukan is_end=True; startsWith hanya memerlukan jalur prefiks tersebut ada.
class Trie:
def __init__(self):
self.root = {}
def insert(self, word):
node = self.root
for c in word:
if c not in node:
node[c] = {}
node = node[c]
node['#'] = True # '#' marks word end
def search(self, word):
node = self.root
for c in word:
if c not in node: return False
node = node[c]
return '#' in node
def startsWith(self, prefix):
node = self.root
for c in prefix:
if c not in node: return False
node = node[c]
return True
t = Trie()
t.insert('apple')
print(t.search('apple')) # True
print(t.search('app')) # False
print(t.startsWith('app')) # TrueMenggunakan '#' sebagai Penanda Akhir (Trie Berbasis Kamus)
Jalan pintas yang elegan menyimpan Trie sebagai kamus bertingkat dengan kunci penanda khusus seperti '#' untuk menandai akhir kata, sehingga tidak memerlukan kelas TrieNode. Cara ini ringkas dan cocok untuk wawancara, tetapi sedikit kurang mudah dibaca daripada objek TrieNode eksplisit. Kedua implementasi dapat diterima; versi kamus lebih cepat ditulis ketika berada di bawah tekanan waktu.
Prefiks Bersama Terpanjang dengan Trie
Untuk menemukan prefiks bersama terpanjang dari daftar teks, lakukan insert pada semua teks ke dalam Trie, lalu telusuri dari akar dengan mengikuti satu-satunya jalur yang ada selama: (1) simpul saat ini memiliki tepat satu anak, dan (2) is_end bernilai salah. Berhenti ketika salah satu kondisi tidak lagi terpenuhi. Jalur yang diikuti merupakan prefiks bersama terpanjang.
class TrieNode:
def __init__(self):
self.children = {}
self.is_end = False
def longest_common_prefix(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.is_end = True
prefix = []
node = root
while len(node.children) == 1 and not node.is_end:
char, node = next(iter(node.children.items()))
prefix.append(char)
return ''.join(prefix)
print(longest_common_prefix(['flower','flow','flight'])) # 'fl'
print(longest_common_prefix(['dog','racecar','car'])) # ''Masalah Penggantian Kata
Penggantian Kata (LeetCode 648): diberikan kamus kata dasar dan sebuah kalimat, ganti setiap kata dalam kalimat dengan kata dasar yang cocok dan paling pendek dari kamus. Lakukan insert pada semua kata dasar ke dalam Trie. Untuk setiap kata dalam kalimat, telusuri Trie hingga menemukan akhir kata dasar — gunakan kata dasar tersebut sebagai pengganti. Jika tidak ada kata dasar yang cocok, pertahankan kata asli. Operasi ini berjalan dalam O(total karakter), dibandingkan dengan pencarian menyeluruh O(n × m).
class TrieNode:
def __init__(self):
self.children = {}
self.is_end = False
def replaceWords(dictionary, sentence):
root = TrieNode()
for word in dictionary:
node = root
for c in word:
if c not in node.children:
node.children[c] = TrieNode()
node = node.children[c]
node.is_end = True
def find_root(word):
node = root
for i, c in enumerate(word):
if c not in node.children: break
node = node.children[c]
if node.is_end:
return word[:i+1]
return word
return ' '.join(find_root(w) for w in sentence.split())
print(replaceWords(['cat','bat','rat'], 'the cattle was rattled by the battery'))Masalah Pasangan Penjumlahan Peta
Penjumlahan Peta (LeetCode 677): lakukan insert pada pasangan kunci-nilai dan kembalikan jumlah semua nilai yang kuncinya memiliki prefiks tertentu. Tambahkan bidang val pada setiap TrieNode. Untuk insert, telusuri hingga akhir lalu tetapkan nilainya; untuk kueri penjumlahan, telusuri hingga simpul akhir prefiks dan jumlahkan semua bidang val di bawahnya dengan DFS. Sebagai alternatif, simpan jumlah kumulatif di setiap simpul selama insert untuk kueri O(p).
Menerapkan Pelengkapan Otomatis dengan Hasil Terbatas
Dalam sistem pelengkapan otomatis produksi, mengembalikan semua kata yang memiliki awalan tertentu tidak praktis ketika ribuan kata cocok. Sebagai gantinya, gunakan tumpukan maksimum berukuran k selama penelusuran DFS: pertahankan k kata dengan skor tertinggi yang ditemukan sejauh ini. Hentikan cabang DFS lebih awal jika cabang tersebut tidak mungkin memuat kata yang termasuk k teratas (pemangkasan berdasarkan batas atas skor). Dengan cara ini, kompleksitasnya menjadi O(p + k × log k) per kueri untuk k saran — jauh lebih baik daripada mengumpulkan semua kecocokan.
Pemeriksaan Singkat
Uji pemahaman Anda tentang konsep Struktur Data & Algoritma — Persiapan Wawancara Pemrograman dari pelajaran ini.
Ringkasan Pelajaran
Dalam pelajaran ini Anda telah mempelajari: pemeriksaan awalan menelusuri jalur awalan dan mengembalikan nilai benar jika jalur tersebut ada — pemeriksaan penanda akhir tidak diperlukan, DFS pelengkapan otomatis mengumpulkan semua kata dari simpul akhir awalan dengan menambahkan karakter saat penelusuran menurun, dan penambahan atribut berupa jumlah atau nilai pada simpul memungkinkan kueri jumlah dan saran k teratas. Selanjutnya, kita akan menambahkan pencocokan karakter pengganti dan ekspresi reguler ke trie.
Pertanyaan yang Sering Diajukan
Apakah pelajaran “Pencarian Awalan dan Starts-With” gratis?
Ya — teks lengkap “Pencarian Awalan dan Starts-With” gratis dibaca di sini di web. Untuk praktiknya secara interaktif (editor kode bawaan dan tutor AI 24/7) dan buka sisa kursus Coding Interview Prep, upgrade ke CoddyKit PRO. Kursus Coding Interview Prep mencakup 4 pelajaran total.
Apa yang akan aku pelajari di “Pencarian Awalan dan Starts-With”?
Tambahkan metode starts_with yang mengembalikan true jika ada kata yang disisipkan dan memiliki awalan tertentu yang sama, lalu gunakan untuk mengimplementasikan saran pelengkapan otomatis Kamu berlatih Coding 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 Coding Interview Prep?
Tidak diperlukan pengalaman sebelumnya. Coding 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 2 dari 4.
Berapa lama pelajaran “Pencarian Awalan dan Starts-With” 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 Coding Interview Prep ini?
Ya. Setiap pelajaran Coding 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