Practice: Design Add and Search Words

Problem: https://leetcode.com/problems/design-add-and-search-words-data-structure/

Recognition reminder: this is a design problem, and it is Implement Trie with one twist that changes everything about search. You add words and you search for them, but a search query may contain ., which matches any single character. The lesson is that a plain forward walk works for concrete characters, but at a . you must branch into every child and succeed if any branch does, which turns search into a small depth-first search over the trie with the query index as the depth.

Before you start (the five-beat rhythm)

  1. Your Pattern Cards for this week are already written (tries and intervals).
  2. Name the pattern aloud and write your approach as a plain-English comment before any code.
  3. Struggle floor: 25 minutes unaided. No hints, no AI, no Discuss tab.
  4. If stuck past the floor, ask the tutor for a hint. Six rungs, one per ask.
  5. Debrief in your commit message before moving to the next problem.

Your target

Fill these in yourself before you look at anyone else’s solution:

Target time complexity of search (consider the worst case for a query of all dots):  ____
Target space complexity:                                                             ____

addWord is the same walk as a trie insert. The interesting cost is search: a query with no dots walks one path, but a query made entirely of dots has to consider every branch at every level. Think about what the worst-case query does to the number of nodes you visit, and say it in terms of the trie’s branching.

The interface you implement

Write a class WordDictionary in a file named solution.py in this folder (your own work repo, not the course repo). It supports:

WordDictionary()             # initialize an empty data structure
addWord(word: str)           # add word (no return value)
search(word: str) -> bool    # True if any added word matches word; a '.' in
                             # word matches any single letter

The method names are exactly addWord and search (matching LeetCode). Added words are lowercase English letters; a search query is lowercase letters and possibly ., exactly as the LeetCode problem guarantees.

Where your code goes

This folder ships only the problem spec and a provided-example test (tests/test_provided.py). Because this is a design problem, the test does not call one function; it drives your WordDictionary through the operation sequence from the LeetCode example and checks each output. Run it locally before you submit to LeetCode’s judge. The judge is the oracle; the tutor will not confirm your answer by reading it.

Debrief (paste into your commit message) 

1. What pattern did this turn out to be?
2. What was the trigger phrase or input shape that should have made me reach for it?
3. What was the time and space complexity, and what would dominate at scale?
4. What edge case would have broken my first attempt?
5. What would I do differently in three days when I see this cold?