Implement Trie (Prefix Tree)
Küçük harfli sözcükler için üç işlemli bir trie (önek ağacı) oluştur: insert w, w sözcüğünü ekler; search w, w sözcüğünün kendisinin eklenip eklenmediğini belirtir ve startsWith p, eklenen herhangi bir sözcüğün p ile başlayıp başlamadığını belirtir. Bir sözcük, kendisinin de öneki sayılır.
i işlemi, words[i] üzerinde ops[i] işlemidir. İşlemleri boş bir trie üzerinde sırayla çalıştır ve her biri için bir dize döndür: ekleme için "null", arama veya startsWith için "true" ya da "false".
Fonksiyon
- opsstring-array
- işlemler, yürütüldükleri sırayla
- wordsstring-array
- her işlem için sözcük veya önek
- Döndürürstring-array
- işlem başına metin olarak bir yanıt
Kısıtlar
1 ≤ ops.length ≤ 2000words.length == ops.length- Her
ops[i],insert,searchveyastartsWithşeklindedir. 1 ≤ words[i].length ≤ 20words[i]yalnızca küçük İngilizce harfler içerir.
Örnekler
- Girdi
- ops = ["insert", "search", "startsWith", "insert", "search"]words = ["card", "car", "car", "car", "car"]
- Çıktı
- ["null", "false", "true", "null", "true"]
- Açıklama
car,cardile başladığı içinstartsWith carsonucu"true"olur; ancakcarhiç eklenmediği için ilk arama"false"sonucunu verir.insert carişleminden sonra arama onu bulur.
- Girdi
- ops = ["insert", "insert", "startsWith", "search", "startsWith", "search", "startsWith"]words = ["tea", "ten", "te", "te", "tex", "ten", "tea"]
- Çıktı
- ["null", "null", "true", "false", "false", "true", "true"]
- Açıklama
- Her iki sözcük de
teile başlıyor, ancak hiçbiri tam olaraktedeğil; bu nedenle startsWith"true", arama ise"false"değerini verir. Hiçbir sözcüktexile başlamıyor veteakendisinin ön ekidir.
- Girdi
- ops = ["search", "startsWith", "insert", "search", "startsWith", "startsWith"]words = ["dog", "d", "dog", "dog", "dogs", "do"]
- Çıktı
- ["false", "false", "null", "true", "false", "true"]
- Açıklama
- Boş trie üzerinde her iki sorgu da
"false"sonucunu verir.insert dogişleminden sonra arama onu bulur, hiçbir sözcükdogsile başlamaz vedo,dogile başlar.
Ek soru
Depolanmış kaç farklı sözcüğün p ile başladığını döndüren bir countPrefix p işlemini yine O(L) zamanda nasıl eklersin?
İpuçları
Tek tek açın. Her biri biraz daha fazlasını gösterir.
Tam sözcüklerden oluşan bir küme,
searchsorgusunu tek aramada yanıtlar, ancak her birini kontrol etmeden herhangi bir sözcüğünteile başlayıp başlamadığını söyleyemez. Aynı şekilde başlayan sözcükler, bu başlangıç için depolama alanını paylaşsaydı ne olurdu?Her düğümün bir öneki temsil ettiği ve ardından gelebilecek her harf için bir çocuk bağlantısı bulunan bir ağaç oluşturun. Bir sözcük, kökten başlayan bir yoldur. Her düğüme, kayıtlı bir sözcüğün tam o noktada bitip bitmediğini belirten bir işaret verin.
Her işlem harfler üzerinde kökten başlayarak ilerler.
inserteksik düğümleri oluşturur ve sonuncusundaki bayrağı ayarlar.startsWithilerleme sona ulaştığında başarılı olur;searchise durduğu düğümde bayrağın ayarlanmış olmasını da gerektirir.
Çözüm
Bir hash kümesi search sorgusunu yanıtlar, ancak başlangıç kavramına sahip değildir; bu nedenle startsWith her kelimeyi tarar. Bir trie, her kelimeyi kökten başlayan bir harf yolu olarak saklar: aynı şekilde başlayan kelimeler ortak bir yolu paylaşır ve bir işaret, saklanan bir kelimenin nerede bittiğini belirtir. Her iki sorgu da en fazla L bağlantıdan oluşan tek bir geçişe dönüşür.
Kelimelerin bir listesini tut ve onu tara
Sezgi
Eklenen her sözcüğü bir listede tut. search w, w değerini depolanan her sözcükle karşılaştırır ve startsWith p, depolanan herhangi bir sözcüğün p ile başlayıp başlamadığını kontrol eder. Tanımı doğrudan sınadığı için doğrudur. Depolanan n sözcük varsa, her sorgu en fazla L harf içeren en fazla n karşılaştırma gerektirir: 1.000 sözcük ve 1.000 sorgu, bir milyon dize karşılaştırması demektir.
Algoritma
- Boş bir listeyle başla.
insert w:w'yi sona ekle.search w: saklanan bir kelimeninw'ye eşit olup olmadığını döndür.startsWith p: saklanan bir kelimeninpile başlayıp başlamadığını döndür.
def trieOps(ops, words):
stored = []
result = []
for op, word in zip(ops, words):
if op == "insert":
stored.append(word)
result.append("null")
elif op == "search":
found = any(s == word for s in stored)
result.append("true" if found else "false")
else:
found = any(s.startswith(word) for s in stored)
result.append("true" if found else "false")
return resultBir trie: çocuk bağlantıları ve bitiş bayrağı
Sezgi
Her düğüm, kökten kendisine giden yol üzerindeki harflerden oluşan bir öneki temsil eder. Gelebilecek her harf için bir çocuk bağlantısı (26 yuva veya bir eşleme) ve kayıtlı bir sözcüğün tam olarak o noktada bitip bitmediğini belirten bir isEnd bayrağı tutar. tea eklemek t, te ve tea düğümlerini oluşturur; ardından ten eklemek yalnızca ten düğümünü ekler, çünkü iki sözcük te yolunu paylaşır.
Eksik bir bağlantıyla karşılaşan bir gezinme, bu harflerle başlayan kayıtlı hiçbir sözcük olmadığını kanıtlar: tex, x bağlantısı olmayan te noktasında durur. Sona ulaşan bir gezinme, sorguya karşılık gelen düğümde durur; bu nedenle startsWith true olur ve search bayrağın değerini verir. te düğümü vardır ancak bayrağı kapalıdır, bu yüzden search te false olur. Kayıtlı sözcük sayısı ne olursa olsun her işlem en fazla L bağlantıyı izler ve trie, her farklı önek için bir düğüm tutar.
Algoritma
- Çocuk bağlantısı olmayan ve
isEnddeğeri kapalı olan bir kök oluşturun. insert w: Kökten başlayarak her harf için bağlantıyı izleyin; eksikse düğümü oluşturun. Son düğümdeisEnddeğerini açık olarak ayarlayın.find(p): Kökten başlayarak her harf için bağlantıyı izleyin; herhangi biri eksikse hemen hiçbir şey döndürmeyin, aksi hâlde ulaşılan düğümü döndürün.search w:find(w)çağrısıisEnddeğeri ayarlanmış bir düğüm döndürdüğünde true olur.startsWith p:find(p)çağrısı bir düğüm döndürdüğünde true olur.
class TrieNode:
def __init__(self):
self.children = {} # letter -> TrieNode
self.is_end = False # does a stored word end at this node?
class Trie:
def __init__(self):
self.root = TrieNode()
def insert(self, word):
node = self.root
for ch in word:
if ch not in node.children:
node.children[ch] = TrieNode()
node = node.children[ch]
node.is_end = True
def _find(self, prefix):
# Follow the letters from the root; None as soon as a link is missing.
node = self.root
for ch in prefix:
node = node.children.get(ch)
if node is None:
return None
return node
def search(self, word):
node = self._find(word)
return node is not None and node.is_end
def starts_with(self, prefix):
return self._find(prefix) is not None
def trieOps(ops, words):
trie = Trie()
result = []
for op, word in zip(ops, words):
if op == "insert":
trie.insert(word)
result.append("null")
elif op == "search":
result.append("true" if trie.search(word) else "false")
else:
result.append("true" if trie.starts_with(word) else "false")
return result
Tuzaklar ve uç durumlar
- Yol mevcut olduğunda
searchyanıtının her zaman true olmasına izin vermek.insert cardişleminden sonracaryolu mevcuttur, ancaksearch carfalse olmalıdır. isEnddeğerini yalnızca yeni oluşturulan düğümlerde ayarlamak.cardssonrasındacardeklemek hiçbir şey oluşturmaz, ancak son düğümün yine de bayrağına ihtiyacı vardır.- Bağlantı zaten mevcutken yeni bir çocuk oluşturmak. Yeni bir
tdüğümüyleteneklemek,teaöğesini kaybettirir. - Yolun sonunu geçecek şekilde okumak. Yalnızca
sunsaklanmışsastartsWith sunny, ilk eksik bağlantıda durmalı ve false yanıtını vermelidir.
Sıkça sorulan sorular3
Bir trie'nin zaman karmaşıklığı nedir?
Ekleme, arama ve startsWith işlemlerinin her biri harf başına bir bağlantıyı takip eder; bu nedenle, depolanan kelime sayısı ne olursa olsun, uzunluğu L olan bir kelime için O(L) zaman alır. Alan kullanımı, toplamda eklenen T harf için O(T) düğümdür; her düğüm en fazla 26 alt düğüm bağlantısı tutar.
Hash kümesi yerine neden trie kullanılır?
Bir hash set, tam sözcükleri O(L) süresinde bulur; ancak her sözcüğü taramadan bir önek sorusunu yanıtlayamaz. Her öneki ikinci bir sette saklamak, tek bir 20 harfli sözcük için 210 harfe mal olur. Bir trie, paylaşılan her öneki bir kez saklar ve her iki soruyu da tek bir geçişle yanıtlar.
Bir trie düğümü 26 bağlantıdan oluşan bir dizi mi yoksa bir hash haritası mı kullanmalı?
Dizi, bir çocuğu tek bir indeksle bulur ancak tek çocuğu olan bir düğüm için bile düğüm başına 26 yuva gerektirir. Map yalnızca mevcut çocukları saklar ve her harf için bir karma değeri maliyetiyle herhangi bir alfabe için çalışır. Küçük harfli İngilizce için ikisi de işe yarar; Unicode veya seyrek trie yapılarında map bellek tasarrufu sağlar.
Benzer problemler
Aynı fikirleri kullanan problemler. İki üçünü çözmek bir kalıbı kalıcı hale getirir.
def trieOps(ops, words):
# Kodu buraya yazınTest #1
Test #2
Test #3
Argümanlar
ops = ["insert", "search", "startsWith", "insert", "search"] words = ["card", "car", "car", "car", "car"]
Beklenen Çıktı
["null", "false", "true", "null", "true"]