Carian Awalan dan Starts-With
Tambahkan kaedah starts_with yang mengembalikan true jika mana-mana perkataan yang disisipkan berkongsi awalan tertentu, kemudian gunakannya untuk melaksanakan cadangan autolengkap.
Carian Awalan dan Starts-With ialah pelajaran Persediaan Temu Duga Pengaturcaraan percuma di CoddyKit. Ini ialah pelajaran 2 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.
Kuasa Pertanyaan Awalan
Kelebihan utama Trie berbanding peta cincang ialah pertanyaan awalan yang cekap. Pertanyaan awalan menjawab soalan seperti 'berapa banyak perkataan yang disimpan bermula dengan awalan ini?', 'apakah semua perkataan yang disimpan dengan awalan ini?', atau sekadar 'adakah wujud mana-mana perkataan dengan awalan ini?'. Pertanyaan ini mengambil O(p), dengan p sebagai panjang awalan, tanpa bergantung pada jumlah keseluruhan perkataan yang disimpan — menjadikan Trie sesuai untuk autocomplete dan cadangan carian.
Kaedah starts_with
starts_with(prefix) memulangkan True jika mana-mana perkataan yang disimpan bermula dengan awalan yang diberikan. Jelajahi Trie dengan mengikuti setiap aksara awalan. Jika semua aksara boleh diikuti tanpa sisi yang hilang, awalan itu wujud dan sekurang-kurangnya satu perkataan bermula dengannya. Pelaksanaannya sama seperti search, kecuali kita memulangkan True sebaik sahaja selesai menjelajah — kita tidak menyemak 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: Mencari Semua Perkataan dengan Awalan
Untuk melaksanakan autocomplete, jelajah hingga nod hujung awalan, kemudian lakukan DFS atau BFS dari nod itu untuk mengumpulkan semua perkataan yang bercabang daripadanya. Tambahkan awalan pada permulaan setiap akhiran yang dikumpulkan untuk membina semula perkataan penuh. Operasi ini mengambil O(p + W), dengan W sebagai jumlah aksara dalam semua perkataan yang sepadan.
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']Memulangkan Cadangan yang Diisih
Untuk autocomplete terisih, jelajah anak mengikut susunan abjad semasa DFS, iaitu ulang melalui sorted(node.children.items()). Oleh sebab anak disimpan dalam kamus, kaedah ini menambah kos tambahan O(saiz abjad × kedalaman) tetapi menjamin hasil yang disusun secara leksikografi. Trie berasaskan tatasusunan sentiasa menjelajah anak mengikut susunan abjad kerana indeks 0-25 telah tersusun.
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')Cadangan Autocomplete Top-K
Untuk cadangan top-k berdasarkan kekerapan, tambahkan pada setiap nod bilangan kali perkataan yang berakhir di situ telah dicari. Semasa mengumpulkan cadangan, gunakan timbunan maksimum bersaiz k. Ini mengurangkan set hasil DFS daripada O(W) kepada O(k) tanpa membina semua padanan. Enjin carian dunia sebenar menggabungkan jelajah awalan Trie dengan data kekerapan untuk menghasilkan cadangan yang pantas dan relevan.
Melaksanakan Trie untuk LeetCode 208
LeetCode 208, 'Melaksanakan Trie (Pokok Awalan)', meminta tepat perkara berikut: insert(word), search(word) yang memulangkan boolean padanan tepat, dan startsWith(prefix) yang memulangkan boolean padanan awalan. Ini ialah pelaksanaan Trie piawai. Ingat: search memerlukan is_end=True; startsWith hanya memerlukan laluan awalan itu wujud.
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 Kamus)
Pendekatan ringkas yang menarik menyimpan Trie sebagai kamus bersarang dengan kunci penanda khas seperti '#' untuk menandakan hujung perkataan, sekali gus menghapuskan keperluan terhadap kelas TrieNode. Kaedah ini padat dan sesuai untuk temu duga, tetapi sedikit kurang mudah dibaca berbanding objek TrieNode yang jelas. Kedua-dua pelaksanaan boleh diterima; versi kamus lebih pantas untuk ditulis apabila masa terhad.
Awalan Sepunya Terpanjang Menggunakan Trie
Untuk mencari awalan sepunya terpanjang bagi senarai rentetan, sisipkan semua rentetan ke dalam Trie, kemudian jelajah dari akar dengan mengikuti laluan tunggal yang wujud selagi: (1) nod semasa mempunyai tepat satu anak, dan (2) is_end ialah False. Berhenti apabila mana-mana syarat tidak lagi dipenuhi. Laluan yang diikuti ialah awalan sepunya 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 Perkataan
Penggantian Perkataan (LeetCode 648): diberikan kamus perkataan akar dan satu ayat, gantikan setiap perkataan dalam ayat dengan akar padanan terpendek daripada kamus. Sisipkan semua akar ke dalam Trie. Bagi setiap perkataan dalam ayat, jelajah Trie sehingga hujung akar ditemui — pulangkan akar itu sebagai pengganti. Jika tiada akar sepadan, kekalkan perkataan asal. Kaedah ini berjalan dalam O(jumlah aksara), berbanding O(n × m) bagi kaedah cuba habis-habisan.
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 Jumlah Peta
Jumlah Peta (LeetCode 677): sisipkan pasangan kunci-nilai dan pulangkan jumlah semua nilai yang keys-nya mempunyai awalan tertentu. Tambahkan medan val pada setiap TrieNode. Untuk insert, jelajah hingga hujung dan tetapkan nilainya; untuk pertanyaan jumlah, jelajah hingga nod hujung awalan dan jumlahkan semua medan val di bawahnya menggunakan DFS. Sebagai alternatif, simpan jumlah terkumpul dalam setiap nod semasa penyisipan untuk pertanyaan O(p).
Melaksanakan Pelengkapan Automatik dengan Hasil Terhad
Dalam sistem pelengkapan automatik pengeluaran, mengembalikan semua perkataan yang mempunyai awalan adalah tidak praktikal apabila ribuan perkataan sepadan. Sebaliknya, gunakan timbunan maksimum bersaiz k semasa penjelajahan DFS: kekalkan k perkataan dengan skor tertinggi yang ditemui setakat ini. Hentikan cabang DFS lebih awal jika cabang itu tidak mungkin mengandungi perkataan k teratas (pemangkasan berdasarkan had atas skor). Ini memberikan O(p + k × log k) bagi setiap pertanyaan dengan k cadangan — jauh lebih baik daripada mengumpulkan semua padanan.
Semakan Pantas
Uji pemahaman anda tentang konsep Struktur Data & Algoritma — Persediaan Temu Duga Pengekodan daripada pelajaran ini.
Ringkasan Pelajaran
Dalam pelajaran ini anda mempelajari: starts_with merentasi laluan awalan dan mengembalikan Benar jika laluan itu wujud — tidak perlu menyemak penanda akhir, pelengkapan automatik mengumpulkan semua perkataan daripada nod hujung awalan melalui DFS dengan menambah aksara semasa menurun, dan menambah nod dengan kiraan atau values membolehkan pertanyaan jumlah dan cadangan k teratas. Seterusnya, kita menambah padanan aksara kad bebas dan ungkapan nalar pada pokok awalan.
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 Awalan dan Starts-With” percuma?
Ya — teks penuh “Carian Awalan dan Starts-With” 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 Awalan dan Starts-With”?
Tambahkan kaedah starts_with yang mengembalikan true jika mana-mana perkataan yang disisipkan berkongsi awalan tertentu, kemudian gunakannya untuk melaksanakan cadangan autolengkap. 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 2 daripada 4.
Berapa lamakah pelajaran “Carian Awalan dan Starts-With” 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