Problem 211

Abstract / Summary

Design a data structure that can add words and search for words with dots representing any sequence of characters.

Note

The full problem description, including helpful examples, can be found on LeetCode.

Python 0211.py

class WordDictionary:
    # "!" marks end of word
    def __init__(self):
        self.root = {}

    def addWord(self, word: str) -> None:
        node = self.root
        for first in word:
            if first not in node:
                node[first] = {}
            node = node[first]
        node["!"] = {}

    def locate(self, node, word):
        if not word:
            return "!" in node

        first = word[0]
        if first == ".":
            for i in node:
                if self.locate(node[i], word[1:]):
                    return True
        elif first in node:
            return self.locate(node[first], word[1:])

        return False

    def search(self, word: str) -> bool:
        return self.locate(self.root, word)
29 lines | 779 bytes | submitted September 4, 2023 | GitHub   4% comment ratio | tab size 4 | low complexity

Difficulty

This problem is ranked as
easy medium hard

and has an acceptance rate of about 49% (1+ million submissions).

Typical patterns to solve this problem:
  • Depth First Search
  • Design
  • String
  • Trie
I solved 663 easy, 1250 medium and 309 hard problems

AI Disclaimer

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.
LeetCode profile | GitHub repo

Code Walkthrough

Overview

The provided implementation defines a WordDictionary class that stores a collection of words and supports search queries with wildcard support (. representing any single character). Internally the class builds a trie (prefix tree) using nested Python dictionaries. Each node in the trie corresponds to a character, and a special sentinel key "!" marks the termination of a complete word. The public interface consists of three methods: the constructor, addWord, and search. The recursive helper locate performs the actual matching logic, handling both exact character matches and wildcard branches.

Core Components

Constructor

The constructor initializes the root of the trie as an empty dictionary. This root serves as the entry point for all insertions and look-ups.

def __init__(self):
    self.root = {}

Adding a Word

addWord iterates over each character of the input string. For each character it ensures that a corresponding child dictionary exists; if not, a new empty dictionary is created. The traversal pointer node moves deeper into the trie with each character. After processing the final character, the sentinel key "!" is inserted to indicate that a complete word ends at this node.

def addWord(self, word: str) -> None:
    node = self.root
    for first in word:
        if first not in node:
            node[first] = {}
        node = node[first]
    node["!"] = {}

Recursive Search Helper

locate receives a current trie node and the remaining portion of the search pattern. The base case occurs when the pattern is empty; the method returns True only if the sentinel "!" is present in the current node, confirming that a stored word exactly matches the consumed characters.

When the first character of the pattern is a literal (non-wildcard), the method proceeds down the matching child node, if it exists, and continues recursion with the rest of the pattern.

If the first character is the wildcard . the method must explore every possible child branch. It iterates over all keys in the current node, recursively invoking locate on each child with the pattern advanced by one character. The moment any branch yields True, the method returns True. If no branch matches, it falls through to return False.

def locate(self, node, word):
    if not word:
        return "!" in node

    first = word[0]
    if first == ".":
        for i in node:
            if self.locate(node[i], word[1:]):
                return True
    elif first in node:
        return self.locate(node[first], word[1:])

    return False

Public Search Method

search simply forwards the request to locate, starting from the root of the trie.

def search(self, word: str) -> bool:
    return self.locate(self.root, word)

Edge Cases Handled

  • Empty Search String - When search receives an empty string, locate immediately checks for the sentinel at the root. This correctly reports True only if an empty word was previously added (which would place "!" directly under the root).

  • Word Consisting Solely of Wildcards - A pattern like "..." triggers the wildcard branch at each recursion level. The implementation explores all possible paths of length three, returning True if any stored word of exactly three characters exists.

  • Duplicate Insertions - Adding the same word multiple times re-writes the sentinel at the same node without altering the structure. The presence of the sentinel remains idempotent, ensuring that subsequent searches still succeed.

  • Prefix Search Without Full Word - Searching for a prefix that does not terminate with a sentinel (e.g., searching "app" after adding "apple" only) returns False because the base case requires "!" in the final node.

  • Wildcard at End of Pattern - A pattern such as "cat." will traverse the exact "c" β†’ "a" β†’ "t" path and then invoke the wildcard branch on the node representing "t". The method correctly matches any stored word that extends "cat" by one additional character.

  • Non-Alphabetic Characters - Since the trie uses dictionary keys directly, any Unicode character present in the input word is treated as a distinct key. The code therefore accommodates words containing digits, symbols, or other characters without special handling.

Performance Optimizations

  • Dictionary-Based Trie Nodes - Using Python’s built-in hash table for each node provides average-case constant-time look-ups for child characters. This choice avoids the overhead of custom node objects and leverages the highly optimized dictionary implementation.

  • Early Termination in Wildcard Branches - The wildcard loop returns immediately upon finding a successful match. This prevents unnecessary exploration of remaining branches once a valid word has been identified, reducing the number of recursive calls in typical scenarios.

  • Sentinel Marker Instead of Boolean Flag - Storing the end-of-word marker as a distinct key ("!") eliminates the need for an additional boolean field per node. The presence check "!" in node is a fast dictionary membership test.

  • Tail Recursion Style - Although Python does not optimize tail recursion, the recursion depth is bounded by the length of the search pattern. The implementation keeps the call stack shallow by processing one character per call, which aligns with the natural depth of the trie.

  • Minimal Object Allocation - The addWord method reuses the same node reference while traversing the trie, creating new child dictionaries only when necessary. This approach minimizes memory churn during bulk insertions.

Interaction Flow

When a client creates a WordDictionary instance, the root dictionary is empty. Each call to addWord expands the trie along the characters of the supplied word, guaranteeing that every prefix of the word is represented as a path in the structure. The sentinel marks the exact endpoint of each stored word.

A subsequent search call invokes locate with the root node and the query pattern. The recursion proceeds character by character, branching on wildcards and following exact matches otherwise. The search concludes successfully only when the pattern is exhausted and the sentinel is present at the current node, ensuring that partial matches do not produce false positives.

The combination of a compact dictionary-based trie, a clear sentinel convention, and early exit on successful wildcard branches yields an implementation that is both space-efficient for typical word sets and responsive to queries that include arbitrary single-character wildcards.

written by openai gpt

ELI5 - Simplified Explanation

Imagine this code is like building a giant library where every shelf connects to another shelf. The whole system starts as an empty room called the root. When you want to store a word in this library, you walk through the room and place each letter onto a shelf. If the letter is not there yet, you build a new little shelf for it. Once you reach the very end of the word, you put a special marker that looks like an exclamation point to show that the word is finished.

To find a word later, you start at the root and look for the first letter. If you find it, you move deeper into the shelf system to find the next letter. Sometimes you might see a dot instead of a letter. A dot is like a magic key that lets you try every single shelf that is currently available. You keep jumping from shelf to shelf following the letters until you run out of them. If you end up on a shelf that has the special exclamation point marker, you know you have found the right word. If you reach a dead end or finish the word without finding that marker, it means the word is not in the library.

written by google gemini

Code Quality

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):
n = 27 | median = 7 | μ = 7.26 | σ = 0.84

Complexity Analysis

not analyzed yet

Other Solutions

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)
author
author solutions
www AlgoMonster C++ Python Java TS
WalkCCC C++ Python Java
leetcode.ca C++ Python C# Java Go
LeetcodeHelp C++ Python Java
MemoryLimitExceeded C++ Python
Progiez C++ Python Java
github aylei Rust
begeekmyfriend C
BigEggStudy C#
bujosa Python
everthis JS
fengvyi C++
gaosq0604 Python
halfrost Go
JoshCrozier JS
keineahnung2345 C++
lennylxx C
linouk23 C++
lkwq007 Python
MacJim C++
ruoru Rust
shreymehul C#
suxrobGM C#
trung-hn Python
varunu28 Java
vli02 C
wisdompeak C++
XiaotaoGuo C++
YuriSpiridonov Python
AlgoMonster C++, Python, Java, TypeScript
WalkCCC C++, Python, Java
leetcode.ca C++, C#, Go, Java, Python
LeetcodeHelp C++, Java, Python
MemoryLimitExceeded Python, C++
Progiez C++, Java, Python
aylei Rust
begeekmyfriend C
BigEggStudy C#
bujosa Python
everthis JavaScript
fengvyi C++
gaosq0604 Python
halfrost Go
JoshCrozier JavaScript
keineahnung2345 C++
lennylxx C
linouk23 C++
lkwq007 Python
MacJim C++
ruoru Rust
shreymehul C#
suxrobGM C#
trung-hn Python
varunu28 Java
vli02 C
wisdompeak C++
XiaotaoGuo C++
YuriSpiridonov Python
43 links | 29 authors | 9 languages

Videos

These are a few popular YouTube videos for this problem:
YouTube video 'Design Add and Search Words Data Structure | Made Easy | GOOGLE | Leetcode 211'
codestorywithMIK 26 mins
Design Add and Search Words Data Structure | Made Easy | GOOGLE | Leetcode 211
YouTube video 'Design Add And Search Words Data Structure | Leetcode 211'
Pepcoding 63 mins
Design Add And Search Words Data Structure | Leetcode 211
YouTube video 'LeetCode 211. Add and Search Word - Data structure design Explanation and Solution'
happygirlzt 7 mins
LeetCode 211. Add and Search Word - Data structure design Explanation and Solution
YouTube video 'Design Add and Search Words Data Structure πŸ”₯| Leetcode 211 | Hashmap | Trie'
Ayushi Sharma 20 mins
Design Add and Search Words Data Structure πŸ”₯| Leetcode 211 | Hashmap | Trie
YouTube video 'Design Add and Search Words Data Structure - Leetcode - 211'
Algorithms Made Easy 5 mins
Design Add and Search Words Data Structure - Leetcode - 211
YouTube video 'Design Add and Search Words Data Structure || Trie Data Structure'
Aryan Mittal 12 mins
Design Add and Search Words Data Structure || Trie Data Structure
YouTube video 'Design Add and Search Words Data Structure | Leeetcode 211 | Live coding session  πŸ”₯πŸ”₯πŸ”₯ | Easy Tries'
Coding Decoded 3 mins
Design Add and Search Words Data Structure | Leeetcode 211 | Live coding session πŸ”₯πŸ”₯πŸ”₯ | Easy Tries
YouTube video '211 || Design Add and Search Words Data Structure || C++ || Leetcode Daily Challenge'
CodeFreaks 22 mins
211 || Design Add and Search Words Data Structure || C++ || Leetcode Daily Challenge
YouTube video 'Leetcode 211. Design Add and Search Words Data Structure [ JAVASCRIPT ].'
Web Fusion with Bharadwaj 21 mins
Leetcode 211. Design Add and Search Words Data Structure [ JAVASCRIPT ].
YouTube video 'Google Coding Interview Question | Leetcode 211 | Design Add and Search Words Data Structure'
WorkWithGoogler 35 mins
Google Coding Interview Question | Leetcode 211 | Design Add and Search Words Data Structure
YouTube video 'LeetCode 211: Design Add and Search Words Data Structure | Python Trie Implementation'
Hack Code 14 mins
LeetCode 211: Design Add and Search Words Data Structure | Python Trie Implementation
YouTube video 'Daily Leetcode #668: Jan 28, 2022 - 211. Design Add and Search Words Data Structure'
Programming Live with Larry 11 mins
Daily Leetcode #668: Jan 28, 2022 - 211. Design Add and Search Words Data Structure
YouTube video 'Daily Leetcode #1083: Mar 19, 2023 - 211. Design Add and Search Words Data Structure'
Programming Live with Larry 14 mins
Daily Leetcode #1083: Mar 19, 2023 - 211. Design Add and Search Words Data Structure
YouTube video 'LeetCode 211 - Design Add and Search Words Data Structure [Daily Challenge]'
Code with Carter 14 mins
LeetCode 211 - Design Add and Search Words Data Structure [Daily Challenge]
YouTube video '211. Design Add and Search Words Data Structure | JavaScript | LeetCode Daily Challenge'
LeetCodeWithMonu 21 mins
211. Design Add and Search Words Data Structure | JavaScript | LeetCode Daily Challenge
YouTube video 'Design Add and Search Words Data Structure | LeetCode 211 | Coders Camp'
Coders Camp 20 mins
Design Add and Search Words Data Structure | LeetCode 211 | Coders Camp
YouTube video '77. Leetcode 211. Design Add and Search Words Data Structure : Javascript'
Web Fusion with Bharadwaj 29 mins
77. Leetcode 211. Design Add and Search Words Data Structure : Javascript
YouTube video 'Design Add and Search Words Data Structure - Leetcode 211 - Python'
Lit Code 10 mins
Design Add and Search Words Data Structure - Leetcode 211 - Python
YouTube video 'Day 253: LeetCode Problem 211. Design Add and Search Words Data Structure - Swift'
iOSxBank 17 mins
Day 253: LeetCode Problem 211. Design Add and Search Words Data Structure - Swift
YouTube video 'LeetCode 211 | Design Add and Search Words Data Structure | Java'
Sleepy Cracker 10 mins
LeetCode 211 | Design Add and Search Words Data Structure | Java
20 videos   did my crawler come up with invalid videos ? drop me a line.

Similar Problems

5 similar problems

Solved On The Same Day

4 easy 20 medium
25 solutions   September 4, 2023

Extra

There are a few extra pages giving you some insights into my setup:
  • Tech Stack - my development environment and tools
  • AI - how AI helped me create this website (NOT solving the problems)
  • Progress - progression over time
  • Quality - code quality