Trie untuk Pencarian Awalan
Menyimpan dan mencari awalan kata dengan cepat
Trie untuk Pencarian Awalan adalah pelajaran Coding 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 Coding Interview Prep, dan progresmu tersinkronisasi di web dan aplikasi CoddyKit. Kursus Coding Interview Prep mencakup 4 pelajaran total.
Menyimpan Kata secara Cerdas
Pohon prefiks adalah pohon yang menyimpan kata dengan berbagi prefiks yang sama. Struktur ini membuat pertanyaan tentang prefiks menjadi sangat cepat. 🌳
Mengapa Tidak Cukup Menggunakan Himpunan
Himpunan dapat menjawab pencarian kata lengkap, tetapi pohon prefiks juga dapat menjawab pertanyaan tentang prefiks, misalnya apakah ada kata yang diawali dengan pre.
Simpul dan Sisi
Setiap simpul adalah sebuah posisi dalam suatu kata, sedangkan setiap sisi diberi label karakter pada jalur dari akar.
Anak sebagai Kamus
Di Python, simpul yang paling mudah dibuat adalah kamus yang memetakan karakter ke simpul anaknya. Sederhana dan fleksibel.
root = {}Menyisipkan Kata
Untuk menyisipkan kata, telusuri karakter satu per satu dan buat anak baru jika belum ada.
node = root
for c in word:
node = node.setdefault(c, {})Menandai Akhir Kata
Setelah menyisipkan kata, tetapkan penanda akhir agar Anda dapat membedakan kata lengkap dari sekadar prefiks.
node['#'] = TrueMencari Kata Lengkap
Untuk mencari, ikuti setiap karakter; jika ada langkah yang tidak tersedia, kata tersebut tidak ada. Setelah itu, periksa penanda akhir.
for c in word:
if c not in node:
return False
node = node[c]Memeriksa Prefiks
Pertanyaan tentang prefiks menggunakan penelusuran yang sama, tetapi pemeriksaan penanda akhir dilewati. Jika mencapai simpul terakhir, jawabannya adalah ya.
Kompleksitas Waktu
Penyisipan dan pencarian membutuhkan O(L), yaitu panjang kata, berapa pun jumlah kata yang disimpan. Panjanglah yang menentukan.
Menghitung Kata berdasarkan Prefiks
Simpan jumlah pada setiap simpul untuk segera menjawab berapa banyak kata tersimpan yang memiliki prefiks tertentu.
Kegunaan Pohon Prefiks
Pohon prefiks mendukung pelengkapan otomatis, pemeriksaan kamus, dan persoalan bit dengan XOR maksimum. Struktur ini merupakan andalan dalam persoalan untai di kontes.
Pemeriksaan Singkat
Pastikan Anda memahami biaya pencarian pada pohon prefiks.
Rangkuman: Pohon Prefiks Selesai
Sekarang Anda dapat membuat pohon prefiks, menyisipkan dan mencari dalam O(L), serta menjawab pertanyaan tentang prefiks dan jumlah dengan cepat. 🌟
Belajar Coding Interview Prep dengan tutor AI — gratis
Tulis dan jalankan kode asli di browser kamu, dapatkan bantuan instan dari tutor AI 24/7, dan lanjutkan di mana kamu tinggalkan di web atau aplikasi.
- Kursus
- 90
- Pelajaran
- 360
Pertanyaan yang Sering Diajukan
Apakah pelajaran “Trie untuk Pencarian Awalan” gratis?
Ya — teks lengkap “Trie untuk Pencarian Awalan” 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 “Trie untuk Pencarian Awalan”?
Menyimpan dan mencari awalan kata dengan cepat 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 4 dari 4.
Berapa lama pelajaran “Trie untuk Pencarian Awalan” 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
- Fungsi Awalan KMP
- Hashing String Polinomial
- Fungsi Z untuk Pencarian Pola
- Trie untuk Pencarian Awalan