Prefix tree işlemleri
Görev tanımı
Problem
Küçük harfli kelimeler için üç işlemli bir trie kur. insert(word) bir kelimeyi saklar. has_word(word) tam olarak o kelimenin saklanıp saklanmadığını bildirir. has_prefix(prefix) saklanan herhangi bir kelimenin verilen boş olmayan prefix (önek) ile başlayıp başlamadığını bildirir. Her işlem, kaç kelime saklanmış olursa olsun argümanının uzunluğuyla orantılı zamana mal olmalı.
Örnekler
Input: insert("apple"), has_word("apple"), has_word("app"), has_prefix("app")
Output: True, False, True
Neden: "app" saklanan bir kelimeyi başlatıyor ama kendisi hiç saklanmadı
Input: insert("apple"), insert("app"), has_word("app")
Output: True
Input: (nothing inserted), has_word("app"), has_prefix("a")
Output: False, False
Neden: edge case: boş bir ağaç hiç kelime ve hiç prefix içermez
İpuçları
0 / 3
Bir prefix'i saklanan her kelimeye karşı kontrol etmek her kelime için zamana mal olur. Aynı şekilde başlayan kelimeler o başlangıcı saklama işini paylaşmalı.
Kelimeleri adım başına bir karakter olacak şekilde iç içe çocuklardan oluşan yollar olarak sakla; böylece ortak bir prefix'i olan kelimeler aynı ilk düğümleri paylaşsın. Bir yolun var olması bir kelimenin orada bitmesiyle aynı değil, bu yüzden bir kelimenin sonunun kendi işaretine ihtiyacı var.
Kökten dolaşıp eksik her çocuğu oluşturarak ekle, sonra son düğüme bir son işareti koy. İki sorgu için de aynı şekilde dolaş ve bir karakterin çocuğu olmadığı anda başarısızlık bildir. Dolaşma biterse prefix sorgusu başarılı olur; kelime sorgusu ayrıca son düğümde son işaretine de ihtiyaç duyar.
- Hedef zaman
- O(L)
- Hedef alan
- O(total characters)
Kısıtlar
- words are lowercase
- prefixes are non-empty
Çözüm
Her düğüm bir karakterden çocuk düğüme giden bir sözlüktür (dict); yani bir kelime kökten bir yoldur ve ortak prefix'ler düğümleri paylaşır. Bir sentinel anahtar saklanan bir kelimenin gerçekten bittiği düğümleri işaretler; saklanan bir "app"i "apple"ın yalnız bir prefix'inden ayıran da bu. İki sorgu da aynı dolaşmayı kullanır ve yalnız sonda sentinel'i isteyip istememeleri bakımından farklılaşır. Her işlem karakter başına bir düğüme dokunur; L uzunluğundaki bir argüman için her biri O(L) tutar, ağaç da O(saklanan toplam karakter) alan kullanır.
class PrefixTree:
def __init__(self):
self.root = {}
def insert(self, word):
node = self.root
for ch in word:
node = node.setdefault(ch, {}) # shared prefixes share nodes
node["$"] = True # a whole word ends here
def _walk(self, s): # the node s leads to, or None
node = self.root
for ch in s:
if ch not in node:
return None
node = node[ch]
return node
def has_word(self, word):
node = self._walk(word)
return node is not None and "$" in node
def has_prefix(self, prefix):
return self._walk(prefix) is not None
t = PrefixTree(); t.insert("apple")
print(t.has_word("apple"), t.has_word("app"), t.has_prefix("app")) # -> True False True
t.insert("app"); e = PrefixTree()
print(t.has_word("app"), e.has_word("app"), e.has_prefix("a")) # -> True False FalseKodda değil de fikirde mi takıldın? Trie temelleri bunu anlatıyor.