Implement Trie (Prefix Tree)

Средняя№208вставка и поиск

Нужно написать класс с тремя методами: insert(word) добавляет слово, search(word) отвечает, добавлено ли ровно это слово, а startsWith(prefix) — начинается ли с этих букв какое-нибудь добавленное слово. Наши вызовы: insert("top"), insert("tea"), search("to"), startsWith("to"), insert("to"), search("to"), startsWith("tu") — они возвращают false, true, true и false; insert ничего не возвращает.

208 Implement Trie (Prefix Tree)Разбор · 1×

Пример: insert("top"), insert("tea"), search("to"), startsWith("to"), insert("to"), search("to"), startsWith("tu"). Ответы копятся под словом, по которому идём.

root
в дереве; двойное кольцо — конец словатолько что добавленпройденный путьтекущий узелвызов возвращает trueнет такой буквы

Создаём Trie(): в дереве пока только корень

01/75
сначала · назад · пуск · шаг
Скорость
1class Trie:
2 function init():
3 root = new node
4 function insert(word):
5 node = root
6 for each ch in word:
7 if ch not in node.children:
8 node.children[ch] = new node
9 node = node.children[ch]
10 node.end = true
11 function search(word):
12 node = find(word)
13 return node is not none and node.end
14 function startsWith(prefix):
15 return find(prefix) is not none
16 function find(word):
17 node = root
18 for each ch in word:
19 if ch not in node.children:
20 return none
21 node = node.children[ch]
22 return node
состояние
word
–
prefix
–
ch
–
node
–
историянажмите шаг, чтобы вернуться

← → шаг · пробел — пауза

Почему это работает

  1. Слово хранится путём из букв от корня, поэтому все слова с одинаковым началом проходят через одни и те же узлы, и find доходит до узла любого префикса за столько шагов, сколько в нём букв.
  2. Дойти до узла — значит только, что какое-то слово так начинается. Целому слову нужна своя отметка конца: в этом вся разница между search и startsWith.
  3. У слова, которое служит началом более длинного, как «to» у «top», путь уже есть. Вставка не добавляет узлов, а только ставит отметку.

Сложность

Время O(L) на вызов, где L — длина его слова: по шагу на букву. Память O(суммы длин вставленных слов): не больше узла на букву и меньше, когда у слов общее начало.

дальшеТеперь реши её сам, без подсказок.

Решить на LeetCode ↗

Задача и её условие принадлежат LeetCode. Здесь — наш пересказ, наш пример и наше решение. Patterns Hero не связан с LeetCode.