Design Add and Search Words Data Structure

Средняя№211поиск с «.»

Нужно написать класс с двумя методами: addWord(word) запоминает слово, а search(word) отвечает, подходит ли под него какое-нибудь запомненное слово, причём «.» в поиске означает любую одну букву. Наши вызовы: addWord("pot"), addWord("pin"), search("p.t") — поиск вернёт true, потому что подходит «pot».

211 Design Add and Search Words Data StructureРазбор · 1×

Пример: addWord("pot"), addWord("pin"), search("p.t"). Потомков пробуем по алфавиту, поэтому точка под «p» пробует «i» раньше «o».

rootaddWord("pot")pot
в дереве; двойное кольцо — конец словатолько что добавленaddWord: пройденный путь; search: ждёт в стеке вызововтекущий узел или вызовтупик: вернул falseвернул true

addWord(«pot»): начинаем с корня

01/58
сначала · назад · пуск · шаг
Скорость
1root = new node // WordDictionary() makes one empty trie
2function addWord(word):
3 node = root
4 for each ch in word:
5 if ch not in node.children:
6 node.children[ch] = new node
7 node = node.children[ch]
8 node.end = true
9function search(word):
10 return match(root, word, 0)
11function match(node, word, i):
12 if i == len(word):
13 return node.end
14 ch = word[i]
15 if ch is '.':
16 for each child in node.children:
17 if match(child, word, i + 1):
18 return true
19 return false
20 if ch not in node.children:
21 return false
22 return match(node.children[ch], word, i + 1)
состояние
word
"pot"
node
root
i
–
ch
–
нажмите шаг, чтобы вернуться

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

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

  1. У обычной буквы не больше одного потомка, куда можно пойти, поэтому поиск идёт по одному пути, как в обычном дереве.
  2. Точка может быть любой буквой, поэтому путём может оказаться любой потомок. match пробует их по одному и сдаётся на точке, только когда все вернули false, поэтому подходящее слово не потеряется.
  3. Когда шаблон кончился, на узле должна стоять отметка конца: дойти до узла — значит только, что какое-то слово так начинается.

Сложность

addWord: время O(L) для слова из L букв, память — не больше O(L) на новые узлы. search: время O(L) без точек; каждая точка может разойтись на 26 потомков, поэтому шаблон с d точками стоит до O(26^d · L). Память O(L) на стек вызовов.

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

Решить на LeetCode ↗

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