Ön Ek Araması ve Şununla Başlar
Eklenen herhangi bir sözcükte verilen ön ekin bulunup bulunmadığını döndüren bir starts_with yöntemi ekleyin ve bunu otomatik tamamlama önerilerini uygulamak için kullanın.
Ön Ek Araması ve Şununla Başlar, CoddyKit'te ücretsiz bir Coding Interview Prep dersidir. Bu, 4 dersinin 2. dersidir. Aşağıdan dersin tamamını ücretsiz okuyabilir, sonra tarayıcıda yerleşik kod editörü ve 7/24 yapay zeka koçu ile uygulamalı olarak pratik yapabilirsin. Bu, Coding Interview Prep öğrenme yolunun bir parçasıdır ve ilerlemeniz web ve CoddyKit uygulaması arasında senkronize olur. Coding Interview Prep kursu toplamda 4 dersten oluşur.
Önek Sorgularının Gücü
Trie yapısının bir karma tabloya göre belirleyici üstünlüğü, verimli önek sorgulamasıdır. Bir önek sorgusu şu sorulardan birini yanıtlar: «saklanan kaç sözcük bu önekle başlıyor?», «bu önekle başlayan saklanmış tüm sözcükler hangileri?» veya basitçe «bu önekle başlayan herhangi bir sözcük var mı?». Bu sorgular, saklanan toplam sözcük sayısından bağımsız olarak önek uzunluğu p için O(p) sürede çalışır; bu da Trie yapılarını otomatik tamamlama ve arama önerileri için ideal kılar.
starts_with Yöntemi
starts_with(prefix), saklanan herhangi bir sözcük verilen önekle başlıyorsa Doğru döndürür. Öneğin her karakterini izleyerek Trie içinde ilerleyin. Eksik bir kenarla karşılaşmadan tüm karakterler izlenebiliyorsa önek mevcuttur ve en az bir sözcük bu önekle başlar. Uygulama search ile aynıdır; tek fark, ilerlemeyi tamamlar tamamlamaz Doğru döndürmemiz ve is_end değerini denetlemememizdir.
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')) # FalseOtomatik Tamamlama: Önekle Başlayan Tüm Sözcükleri Bulma
autocomplete uygulamak için öneğin son düğümüne ilerleyin, ardından o düğümden dallanan tüm sözcükleri toplamak üzere bir DFS (veya BFS) gerçekleştirin. Tam sözcükleri yeniden oluşturmak için toplanan her son ekin başına öneki ekleyin. Bu işlem, W eşleşen sözcüklerdeki toplam karakter sayısı olduğunda O(p + W) sürede çalışır.
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']Sıralanmış Önerileri Döndürme
Sıralanmış otomatik tamamlama için DFS sırasında alt düğümler arasında alfabetik sırayla ilerleyin (sorted(node.children.items()) üzerinde yineleyin). children bir sözlükte saklandığı için bu yaklaşım O(alfabe boyutu × derinlik) ek yük getirir, ancak sonuçların sözlükbilimsel sırada olmasını garanti eder. Dizi tabanlı bir Trie, 0-25 arasındaki dizinler sıralı olduğundan alt düğümler arasında her zaman alfabetik sırayla ilerler.
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')En Sık Kullanılan İlk K Öneri
Sıklığa göre en iyi k öneriyi elde etmek için her düğüme, o düğümde biten sözcüğün kaç kez arandığını belirten bir sayaç ekleyin. Önerileri toplarken k boyutunda bir maksimum yığın kullanın. Böylece O(W) süreli DFS sonuç kümesi, tüm eşleşmeleri bellekte oluşturmadan O(k) boyutuna indirilir. Gerçek dünyadaki arama motorları hızlı ve ilgili öneriler sunmak için Trie önek geçişini sıklık verileriyle birleştirir.
Trie'yi LeetCode 208 İçin Uygulama
LeetCode 208 «Trie'yi Uygulama (Önek Ağacı)» tam olarak şunları ister: insert(word), tam eşleşme boole değerini döndüren search(word) ve önek eşleşme boole değerini döndüren startsWith(prefix). Bu, Trie uygulamasının temel örneğidir. Unutmayın: search için is_end=True gerekir; startsWith için yalnızca önek yolunun mevcut olması yeterlidir.
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')) # TrueSon İşareti Olarak '#' Kullanma (Sözlük Trie'si)
Zarif bir kısayol, Trie'yi sözcük sonlarını işaretlemek için '#' gibi özel bir nöbetçi anahtara sahip iç içe sözlükler biçiminde saklar; böylece bir TrieNode sınıfına gerek kalmaz. Bu yaklaşım kısa ve mülakatlar için uygundur, ancak açık TrieNode nesnelerine göre biraz daha az okunabilirdir. Her iki uygulama da kabul edilebilir; zaman baskısı altında sözlük sürümünü yazmak daha hızlıdır.
Trie Kullanarak En Uzun Ortak Önek
Bir dize listesinin en uzun ortak önekini bulmak için tüm dizeleri Trie'ye ekleyin, ardından kökten başlayarak şu koşullar sağlandığı sürece var olan tek yolu izleyin: (1) geçerli düğümün tam olarak bir alt düğümü vardır ve (2) is_end Yanlış'tır. Koşullardan biri bozulduğunda durun. İzlenen yol, en uzun ortak önektir.
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'])) # ''Sözcükleri Değiştirme Problemi
Sözcükleri Değiştirme (LeetCode 648): kök sözcüklerden oluşan bir sözlük ve bir cümle verildiğinde, cümledeki her sözcüğü sözlükteki eşleşen en kısa kökle değiştirin. Tüm kökleri bir Trie'ye ekleyin. Cümledeki her sözcük için bir kökün sonu bulunana kadar Trie'de ilerleyin ve bu kökü değiştirilecek sözcük olarak döndürün. Hiçbir kök eşleşmezse özgün sözcüğü koruyun. Bu yaklaşım, kaba kuvvetteki O(n × m) yerine O(toplam karakter) sürede çalışır.
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'))Harita Toplamı Çiftleri Problemi
Harita Toplamı (LeetCode 677): anahtar-değer çiftlerini ekleyin ve anahtarları verilen bir önekle başlayan tüm değerlerin toplamını döndürün. Her TrieNode'a bir val alanı ekleyin. Ekleme için sona kadar ilerleyip değeri ayarlayın; toplam sorguları için öneğin son düğümüne ilerleyin ve altındaki tüm val alanlarını DFS ile toplayın. Alternatif olarak, O(p) süreli sorgular için ekleme sırasında her düğümde birikimli toplamı saklayabilirsiniz.
Sınırlı Sonuçlarla Otomatik Tamamlama Uygulama
Üretim ortamındaki otomatik tamamlama sistemlerinde, binlerce kelime eşleştiğinde ön eke sahip tüm kelimeleri döndürmek pratik değildir. Bunun yerine, DFS geçişi sırasında boyutu k olan bir maksimum yığın kullanın: şimdiye kadar bulunan, puanı en yüksek k kelimeyi tutun. En yüksek k içindeki bir kelimeyi barındıramayacakları kesin olan DFS dallarını erkenden durdurun (puan üst sınırına göre budama). Böylece k önerisi için sorgu başına O(p + k × log k) elde edilir; bu, tüm eşleşmeleri toplamaktan çok daha iyidir.
Kısa Değerlendirme
Bu dersteki Veri Yapıları & Algoritmalar — Kodlama Mülakatına Hazırlık konularını ne kadar anladığınızı sınayın.
Ders Özeti
Bu derste şunları öğrendiniz: starts_with, ön ek yolunu dolaşır ve varsa True döndürür; is_end kontrolü gerekmez, otomatik tamamlama DFS'i, karakterleri aşağı doğru inerken ekleyerek ön ekin sonundaki düğümden tüm kelimeleri toplar ve düğümlere sayılar veya değerler eklemek, toplam sorgularını ve en yüksek k önerilerini mümkün kılar. Sırada trie yapısına joker karakter ve düzenli ifade eşleştirmesi eklemek var.
Sıkça Sorulan Sorular
“Ön Ek Araması ve Şununla Başlar” dersi ücretsiz mi?
Evet — “Ön Ek Araması ve Şununla Başlar” dersin tüm metni burada web'de ücretsiz olarak okunabilir. Etkileşimli olarak pratik yapmak (yerleşik kod editörü ve 7/24 yapay zeka koçu) ve Coding Interview Prep kursunun geri kalanını açmak için CoddyKit PRO'ya yükselt. Coding Interview Prep kursu toplamda 4 dersten oluşur.
“Ön Ek Araması ve Şununla Başlar” dersinde ne öğreneceğim?
Eklenen herhangi bir sözcükte verilen ön ekin bulunup bulunmadığını döndüren bir starts_with yöntemi ekleyin ve bunu otomatik tamamlama önerilerini uygulamak için kullanın. Coding Interview Prep ile uygulamalı kodu tarayıcıda doğrudan çalıştırarak pratik yaparsın ve 7/24 yapay zeka koçu dersi çalışırken sorularını yanıtlar.
Coding Interview Prep öğrenmeye başlamak için deneyim gerekli mi?
Önceden deneyim gerekmez. CoddyKit'te Coding Interview Prep, başlangıçtan ileri seviyeye kadar yapılandırıldığı için buradan başlayabilir veya başından başlayıp kendi hızında ilerleme yapabilirsin. Bu, 4 dersinin 2. dersidir.
“Ön Ek Araması ve Şununla Başlar” dersi ne kadar sürer?
Çoğu CoddyKit dersi yaklaşık 5–10 dakika sürer. Her biri kısa ve etkileşimli olduğu için sabit ilerleme yaparsın ve web ile uygulama arasında tam olarak bıraktığın yerden devam edebilirsin.
Bu Coding Interview Prep dersinde kod yazıp çalıştırabilir miyim?
Evet. Her Coding Interview Prep dersi yerleşik bir kod editörü içerir, bu sayede tarayıcıda gerçek kod yazıp çalıştırabilir ve anlık yapay zeka geri bildirimi alırsın — yerel kurulum gerekli değildir.
Bu kursun tüm dersleri
- TrieNode Sınıfı: Ekleme ve Arama
- Ön Ek Araması ve Şununla Başlar
- Trie’da Joker ve Düzenli İfade Araması
- Sözcük Araması II: Trie + Izgarada Geri İzleme