Trees & triesLeetCode 211

Lesson 48 of 76

Design Add and Search Words Data Structure

Design a word dictionary that supports adding words and searching with '.' as a wildcard letter.

Watch on YouTube

Lesson notes

Try it before you watch

Restate the problem in your own words, list the edge cases, and sketch a solution with its running time. Then play the video and compare.

Reveal the key idea

Store words in a trie. When searching, follow the matching child for normal letters and try every child for a '.'.

Pattern: Trees & tries. Most tree problems are a recursive question asked of the left subtree, the right subtree, and the root.

Complexity

Cost of the standard optimal approach for Design Add and Search Words Data Structure
Measure Bound
Time O(L) to add; search can visit the whole trie with wildcards
Extra space O(total characters added)

Walkthroughs often start from a simpler approach first; aim to reach these bounds. New to Big-O? Read understanding algorithmic complexity.