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)
Difficulty
and has an acceptance rate of about 49% (1+ million submissions).
Typical patterns to solve this problem:
- Depth First Search
- Design
- String
- Trie
AI Disclaimer
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.
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
searchreceives an empty string,locateimmediately checks for the sentinel at the root. This correctly reportsTrueonly 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, returningTrueif 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) returnsFalsebecause 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 nodeis 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
addWordmethod reuses the samenodereference 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.
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.
Code Quality
Complexity Analysis
Other Solutions
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 |
Videos
Similar Problems
- problem 208: Implement Trie (Prefix Tree)
- problem 745: Prefix and Suffix Search
- problem 2301: Match Substring After Replacement
- problem 3042: Count Prefix and Suffix Pairs I
- problem 3045: Count Prefix and Suffix Pairs II
Solved On The Same Day
- problem 292: Nim Game
- problem 572: Subtree of Another Tree
- problem 617: Merge Two Binary Trees
- problem 671: Second Minimum Node In a Binary Tree
- problem 152: Maximum Product Subarray
- problem 207: Course Schedule
- problem 210: Course Schedule II
- problem 213: House Robber II
- problem 237: Delete Node in a Linked List
- problem 260: Single Number III
- problem 416: Partition Equal Subset Sum
- problem 437: Path Sum III
- problem 450: Delete Node in a BST
- problem 560: Subarray Sum Equals K
- problem 606: Construct String from Binary Tree
- problem 623: Add One Row to Tree
- problem 652: Find Duplicate Subtrees
- problem 654: Maximum Binary Tree
- problem 655: Print Binary Tree
- problem 662: Maximum Width of Binary Tree
- problem 669: Trim a Binary Search Tree
- problem 687: Longest Univalue Path
- problem 1115: Print FooBar Alternately
- problem 1116: Print Zero Even Odd
Extra
- 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