İçeriğe geç

Prefix tree işlemleri

Kolay#trie#design~20 dk

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

Hedef zaman
O(L)
Hedef alan
O(total characters)

Kısıtlar

  • words are lowercase
  • prefixes are non-empty

Kodda değil de fikirde mi takıldın? Trie temelleri bunu anlatıyor.

Python 3Ctrl+Enter çalıştırır