Design Add and Search Words Data Structure
İki işlemle bir sözcük sözlüğü oluşturun. addWord w sözcüğü w kaydeder. search p, kayıtlı bir sözcüğün p deseniyle eşleşip eşleşmediğini söyler: uzunlukları aynı olmalı ve desenin her konumunda aynı harf ya da herhangi bir harfi temsil eden bir nokta . bulunmalıdır.
i işlemi, sözcük ya da desen words[i] üzerinde ops[i] işlemidir. İşlemleri boş bir sözlükte sırayla uygulayın ve her biri için bir dize döndürün: addWord için "null", search için "true" veya "false".
Fonksiyon
- opsstring-array
- işlemler, yürütüldükleri sırayla
- wordsstring-array
- Eklenecek sözcük veya aranacak kalıp; her işlemde bir tane
- Döndürürstring-array
- işlem başına metin olarak bir yanıt
Kısıtlar
1 ≤ ops.length ≤ 2500words.length == ops.length- Her
ops[i],addWordya dasearchdeğeridir. 1 ≤ words[i].length ≤ 20- Eklenecek sözcük yalnızca küçük İngilizce harflerden oluşur.
- Aranacak bir desen, küçük İngilizce harfler ve en fazla 3 nokta içerir.
Örnekler
- Girdi
- ops = ["addWord", "addWord", "search", "search", "search", "search"]words = ["rose", "rise", "r.se", "ros", "rose.", "..s."]
- Çıktı
- ["null", "null", "true", "false", "false", "true"]
- Açıklama
r.seher iki kelimeyle de eşleşir: nokta,rosesözcüğündeki o harfini verisesözcüğündeki i harfini karşılar. Nokta hiçbir zaman eksik bir harfin yerini tutmaz; bu nedenlerosverose.eşleşmez...s.eşleşir; çünkü her iki kelimenin de üçüncü harfi s'dir.
- Girdi
- ops = ["search", "addWord", "search", "search", "search"]words = ["...", "sky", "...", "s.y", "sk"]
- Çıktı
- ["false", "null", "true", "true", "false"]
- Açıklama
- Sözlük boş başlar, bu yüzden
...hiçbir şey bulamaz.skyeklendikten sonra...ves.yikisi de eşleşir, ancakskçok kısadır.
- Girdi
- ops = ["addWord", "addWord", "search", "search", "search"]words = ["maple", "mango", "ma..o", "m...y", "m.p.e"]
- Çıktı
- ["null", "null", "true", "false", "true"]
- Açıklama
ma..oifadesindeki ilk nokta,maplesözcüğünün p harfi ya damangosözcüğünün n harfi olabilir;maplee harfiyle biter, ancakmangouyar. Hiçbir sözcük y harfiyle bitmediğindenm...yeşleşmez vem.p.e,mapleile eşleşir.
Ek soru
Bir kalıp, boş olanlar da dahil olmak üzere herhangi bir harf dizisini temsil eden * karakterini de içerebiliyorsa search işlevini nasıl genişletirdin?
İpuçları
Tek tek açın. Her biri biraz daha fazlasını gösterir.
Noktalar olmadan, saklanan sözcüklerden oluşan bir hash kümesi her aramayı tek bir aramayla yanıtlayabilirdi. Nokta bunu bozar:
c.t,cat,cotveyacutolabilir. Hangi yapı, bir sözcüğü harf harf takip etmeni ve ardından gelebilecek tüm harfleri görmeni sağlar?Kelimeleri bir trie içinde saklayın ve saklanan bir kelimenin bittiği her düğümde bir işaret bulundurun. Desendeki bir harf tek bir çocuk bağlantısını izler. Nokta herhangi bir harf olabilir; bu nedenle geçerli düğümün her çocuğunu denemeli ve bir dal çıkmaza girdiğinde geri dönmelisiniz.
Özyinelemeli bir
match(node, i)yaz. Desenin sonunda, düğümün bitiş bayrağını döndür. Bir harfte, o çocuğu izle; yoksa başarısız ol. Noktada, herhangi bir çocuk içinmatch(child, i+1)başarılı olur olmaz true döndür; hiçbiri başarılı olmazsa false döndür.
Çözüm
Nokta, aramanın istediği sözcüğü belirtemediği anlamına gelir: ma..o, 676 olası sözcüğü temsil eder ve yalnızca depolanmış olanlar önemlidir. Bir trie'de, aynı şekilde başlayan sözcükler bir yolu paylaşır. Desendeki bir harf tek bir bağlantıyı izler, nokta yalnızca mevcut çocuk düğümlere dallanır ve derinlik öncelikli arama çıkmaz dallardan geri döner.
Örüntüyü depolanan her sözcükle karşılaştır
Sezgi
Eklenen sözcükleri bir listede tut ve her birini şu örüntüye göre sına: uzunlukları aynı olmalı ve her konumda ya nokta ya da aynı harf bulunmalı. Bu, eşleşmenin tanımıdır; kayıtlı her sözcükle karşılaştırılır, böylece yanıt doğru olur.
Her arama tüm listenin maliyetini getirir: O(n·L), en fazla L harften oluşan n sözcük için; nokta içermeyen bir örüntüde bile. 1,250 eklemenin ardından yapılan 1,250 arama, 1,250 × 1,250 = 1,562,500 sözcüğü sınar.
Algoritma
- Eklenen sözcükleri bir listede tutun.
addWord wiçinwdeğerini ekleyin ve"null"kaydını tutun. search piçinpdeğerini aynı uzunluktaki her sözcükle konum konum karşılaştırın; noktanın herhangi bir harfi kabul etmesini sağlayın.- İlk eşleşmede
"true", eşleşme yoksa"false"kaydını tutun.
def matches(pattern, word):
# Same length, and every position holds a dot or the same letter.
if len(pattern) != len(word):
return False
for p, w in zip(pattern, word):
if p != "." and p != w:
return False
return True
def wordDictionaryOps(ops, words):
stored = []
result = []
for op, word in zip(ops, words):
if op == "addWord":
stored.append(word)
result.append("null")
else:
found = any(matches(word, s) for s in stored)
result.append("true" if found else "false")
return resultNoktalar üzerinde derinlik öncelikli arama ile Trie
Sezgi
Sözcükleri bir trie içine yerleştir: rose ve rise r düğümünü paylaşır, ardından o ve i dallarına ayrılır. Bitiş işareti, kayıtlı bir sözcüğün bittiği her düğümü belirtir. Harflerden oluşan bir desen, trie içinde aşağı doğru yapılan tek bir yürüyüştür. Nokta herhangi bir harf olabilir; bu nedenle bir noktada mevcut her çocuk düğümü dene ve eşleşmeye götüren bir düğüm bulur bulmaz true döndür.
ma..o için ma düğümünün p ve n çocukları vardır. p üzerinden ikinci nokta l düğümüne ulaşır ve bu düğümün o çocuğu yoktur; bu yüzden arama geri dönüp n düğümünü dener: g, ardından da mango sözcüğünün bittiği o düğümü.
Bir eşleşme, uzunluğu belirlemek için desenin tamamını işaretli bir düğümde tüketmelidir: ros işaretlenmemiş bir düğümde durur, rose. ise bağlantı kalmayınca sona erer. Bir nokta en fazla 26 dal açar; bu nedenle d nokta en fazla 26^d · L düğümü ziyaret eder ve nokta içermeyen bir desenin maliyeti O(L) olur.
Algoritma
- Her düğümün çocuk bağlantıları ve başlangıçta kapalı olan bir bitiş bayrağı vardır.
addWord wiçin: kökten başlayarakwboyunca ilerle, eksik düğümleri oluştur ve ilerlemenin durduğu yerde bitiş bayrağını ayarla.match(node, i):iörüntünün uzunluğuna eşitse düğümün bitiş bayrağını döndür.p[i]bir harfse, çocuğu eksik olduğunda false döndür; aksi hâldematch(child, i+1)sonucunu döndür. Bir nokta ise, mevcut çocuklardan herhangi biri içinmatch(child, i+1)başarılı olursa true, aksi hâlde false döndür.- Her arama için
match(root, 0), her ekleme için"null"kaydet.
class TrieNode:
def __init__(self):
self.children = {} # letter -> TrieNode
self.is_end = False # does a stored word end at this node?
class WordDictionary:
def __init__(self):
self.root = TrieNode()
def add_word(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 search(self, pattern):
return self._match(self.root, pattern, 0)
def _match(self, node, pattern, i):
# Can the path below node spell pattern[i:] and end on a stored word?
if i == len(pattern):
return node.is_end
ch = pattern[i]
if ch == ".":
# A dot stands for any letter: try each child until one works.
for child in node.children.values():
if self._match(child, pattern, i + 1):
return True
return False
child = node.children.get(ch)
return child is not None and self._match(child, pattern, i + 1)
def wordDictionaryOps(ops, words):
dictionary = WordDictionary()
result = []
for op, word in zip(ops, words):
if op == "addWord":
dictionary.add_word(word)
result.append("null")
else:
result.append("true" if dictionary.search(word) else "false")
return result
Tuzaklar ve uç durumlar
- İlk çocuğun noktaya karar vermesine izin vermek.
ma..oiçinde p dalı başarısız olur ve n dalı başarılı olur; bu nedenle ilk çocuğun sonucunu döndüren kod, önce p'yi denediğinde false yanıtını verir. Yalnızca tüm çocuklar başarısız olduktan sonra false yanıtını verin. - Desen herhangi bir düğümde bittiğinde true yanıtını vermek.
roseeklendikten sonrarosbir düğüme ulaşır, ancak o noktada hiçbir sözcük bitmez. Bitiş bayrağını kontrol edin. - Noktanın eksik bir harfle eşleşmesine izin vermek.
card.,cardsile eşleşir amacardile eşleşmez. - Noktayı bir harf olarak ele almak. 26 yuvalı bir dizide
'.' - 'a'ile indeksleme, dizinin dışından okur; bu nedenle önce nokta olup olmadığını kontrol edin.
Sıkça sorulan sorular3
Kelime Ekleme ve Arama işlemlerinin zaman karmaşıklığı nedir?
L uzunluğunda bir kelime eklemek O(L) sürer; nokta içermeyen bir arama da depolanan kelime sayısından bağımsız olarak aynı süreyi alır. d nokta içeren bir arama en kötü durumda O(26^d · L) sürer. T eklenen harf için bellek kullanımı O(T) düğümdür.
Trie yerine bir hash kümesiyle çözebilir misin?
Evet, bazı ödünlerle. Bir küme, nokta içermeyen bir deseni tek aramada eşleştirir. Noktalar için ya o uzunluktaki saklanan her sözcüğü tararsınız, O(n·L), ya da her noktayı 26 harfin tümüyle doldurup her sonucu ararsınız; üç nokta için 17,576 arama gerekir.
Trie araması özyinelemeli mi yoksa yinelemeli mi olmalı?
İkisi de işe yarar. Özyineleme, desenin her harfi için bir düzey ilerler; burada en fazla 20 olduğundan çağrı yığını küçük kalır. Yinelemeli bir sürüm, (düğüm, konum) çiftlerinden oluşan bir yığını tutar ve bir nokta karşılaşıldığında her çocuğu yığına ekler.
Benzer problemler
Aynı fikirleri kullanan problemler. İki üçünü çözmek bir kalıbı kalıcı hale getirir.
def wordDictionaryOps(ops, words):
# Kodu buraya yazınTest #1
Test #2
Test #3
Argümanlar
ops = ["addWord", "addWord", "search", "search", "search", "search"] words = ["rose", "rise", "r.se", "ros", "rose.", "..s."]
Beklenen Çıktı
["null", "null", "true", "false", "false", "true"]