Prefix arama
Adım 1/9
Üç kelime saklı. Kullanıcı henüz bir şey yazmadı, yani hepsi hâlâ aday.
Fikir
Otomatik tamamlama (autocomplete), "bu bir kelime mi?" sorusundan farklı bir şey sorar. Sorduğu şu: "bununla ne başlıyor?"
Prefix (önek) boyunca bir kez in; bunun maliyeti yazılan karakter başına bir adım. Vardığın düğüm (node), tam olarak o prefix'e sahip kelimeleri tutan bir alt ağacın köküdür; bu yüzden önerileri toplarken sözlüğün geri kalanına hiç dokunmazsın.
Gerçek hayattan örnek
Üç harften sonra kelime öneren bir telefon klavyesi düşün. Tuş vuruşları arasında 200.000 kelimeyi baştan tarayamaz; bu yüzden "cat" için ulaştığı konumu tutar ve sonraki tuşta baştan başlamak yerine bir adım daha atar.
Kod
Sıra sende
Boşluğu doldur.
trie = {"a": {"t": {"$": 1}}}
node = trie
for ch in "ax":
node = node.get(ch)
if node ___ None:
break
print(node) # NoneMini quiz
1 / 3