Design Add And Search Words Data Structure

Asked byFacebookAmazonMicrosoftAppleGoogleByteDance

Problem

Design a data structure that supports adding words and searching for a word, where the search may include the wildcard character '.' that can match any single letter.

Examples

Example 1

Input:addWord("bad"); addWord("dad"); addWord("mad"); search("pad")

Output:false

Example 2

Input:search(".ad"); search("b..")

Output:true, true

Constraints

1 <= word.length <= 25
word consists of lowercase English letters and possibly '.' during search.

Solve it in the editor. Sign in free to run your Python or JavaScript against test cases, get a verdict, and track your attempts.

Solve on FeatCode →

How to approach it: the Tries pattern

A trie (prefix tree) stores strings character by character along tree edges, so words sharing a prefix share the same path. It turns "does any word start with this prefix?" into a walk proportional to the prefix length instead of a scan of every word.

Look for this pattern when

You're repeatedly checking prefixes (autocomplete, spell-check, word search on a grid).
You need to store a large dictionary of words and query it efficiently by prefix.

Read the full Tries guide →

Video walkthroughs

Original problem on LeetCode ↗