Design Add and Search Words Data Structure

Medium#211search with .

Build a class with two methods: addWord(word) stores a word, and search(word) says whether some stored word fits it, where a "." in the search stands for any one letter. Our calls: addWord("pot"), addWord("pin"), search("p.t") — the search returns true, because "pot" fits.

211 Design Add and Search Words Data StructureWalkthrough · 1×

Example: addWord("pot"), addWord("pin"), search("p.t"). Children are tried in letter order, so the dot under "p" tries "i" before "o".

rootaddWord("pot")pot
in the trie; a double ring ends a wordjust addedaddWord: the path so far; search: waiting on the call stackcurrent node or calldead branch: returned falsereturned true

addWord("pot"): start at the root

01/58
restart · back · play · step
Speed
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)
state
word
"pot"
node
root
i
–
ch
–
click a step to go back

← → step · space play/pause

Why it works

  1. A plain letter has at most one child to go to, so the walk stays on one path, as in a normal trie search.
  2. A dot can be any letter, so every child is a possible path. match tries them one by one and only gives up on the dot when all of them returned false, so no stored word that fits is missed.
  3. At the end of the pattern the node must carry the end mark: reaching it only proves that some stored word starts this way.

Complexity

addWord: time O(L) for a word of L letters, memory O(L) at most for its new nodes. search: time O(L) without dots; each dot can branch to up to 26 children, so a pattern with d dots costs up to O(26^d · L). Memory O(L) for the call stack.

nextNow solve it yourself, no hints.

Solve on LeetCode ↗

The problem and its statement belong to LeetCode. Here are our own retelling, example and solution. Patterns Hero is not affiliated with LeetCode.