# LeetCode 211: Design Add and Search Words Data Structure

## Problem Restatement

We need to design a data structure that supports two operations:

| Operation | Meaning |
|---|---|
| `addWord(word)` | Add a word into the data structure |
| `search(word)` | Return whether a word matches the query |

The search query may contain lowercase letters and the special character:

```text
.
```

A dot matches any one lowercase letter.

The official LeetCode problem asks us to implement `WordDictionary` with `addWord` and `search`, where `search` supports `.` as a wildcard matching any letter.

## Input and Output

| Item | Meaning |
|---|---|
| Input | Method calls on a `WordDictionary` object |
| Output | `None` for `addWord`, boolean for `search` |
| Stored data | Words made of lowercase English letters |
| Wildcard | `.` matches exactly one character |

Class shape:

```python
class WordDictionary:

    def __init__(self):
        ...

    def addWord(self, word: str) -> None:
        ...

    def search(self, word: str) -> bool:
        ...
```

## Examples

Example:

```python
wordDictionary = WordDictionary()
wordDictionary.addWord("bad")
wordDictionary.addWord("dad")
wordDictionary.addWord("mad")

wordDictionary.search("pad")
wordDictionary.search("bad")
wordDictionary.search(".ad")
wordDictionary.search("b..")
```

Results:

```python
False
True
True
True
```

Why?

```text
"pad" does not exist
"bad" exists
".ad" matches "bad", "dad", or "mad"
"b.." matches "bad"
```

## Why a Hash Set Is Not Enough

For exact search, a hash set is simple.

```python
words = {"bad", "dad", "mad"}
```

Then:

```python
"bad" in words
```

works in constant time.

But wildcard search is harder.

For:

```python
".ad"
```

we need to check all possible words that could match.

A set alone would require scanning many stored words.

We need a structure that supports prefix traversal and branching.

## Key Insight: Trie Plus DFS

This problem is a direct extension of Trie.

A Trie is good for storing words character by character.

For normal letters, we follow one child.

For the wildcard `.`, we try every possible child.

That wildcard branching naturally becomes DFS.

## Trie Node Design

Each node needs:

| Field | Meaning |
|---|---|
| `children` | Maps character to the next Trie node |
| `is_word` | Marks whether a full word ends here |

Node class:

```python
class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_word = False
```

The `is_word` flag matters because a prefix and a complete word are different.

For example, after adding:

```python
"bad"
```

the path:

```text
b -> a
```

exists, but `"ba"` has not been added as a word.

So:

```python
search("ba")
```

must return `False`.

## Algorithm: addWord

To add a word:

1. Start at the root.
2. For each character:
   - If the child does not exist, create it.
   - Move to that child.
3. After the last character, mark the node as a complete word.

Example:

```python
addWord("bad")
```

Creates this path:

```text
root -> b -> a -> d
```

Then marks the `d` node as a word ending.

## Algorithm: search

Search needs recursion because `.` can branch.

Define a DFS function:

```python
dfs(index, node)
```

Meaning:

```text
Can word[index:] match starting from this Trie node?
```

At each position:

- If the character is a normal letter, follow that child.
- If the character is `.`, try every child.
- If we reach the end of the pattern, return `node.is_word`.

## Walkthrough

Suppose the dictionary contains:

```text
bad
dad
mad
```

Trie shape:

```text
root
├── b -> a -> d
├── d -> a -> d
└── m -> a -> d
```

Search:

```python
".ad"
```

At index `0`, the pattern has `.`.

So DFS tries all root children:

```text
b
d
m
```

Try `b`.

Then remaining pattern is:

```text
ad
```

`a` exists after `b`.

`d` exists after `a`.

End of pattern, and the node is marked as a word.

So return:

```python
True
```

Search:

```python
"pad"
```

At index `0`, the pattern has `p`.

There is no `p` child at the root.

Return:

```python
False
```

## Correctness

The `addWord` method inserts each word as a path from the root to a terminal node. The final node is marked with `is_word = True`, so the structure records exactly which full words have been added.

The `search` method checks whether the query can match any inserted word.

For a normal letter, the next Trie edge must have that exact character. If the edge is missing, no stored word can match that query path.

For `.`, any lowercase letter may match, so the algorithm correctly tries every child node. If any branch succeeds, the wildcard query matches an inserted word.

When the search reaches the end of the query, the algorithm returns `True` only if the current node marks the end of a full inserted word. This prevents prefixes from being accepted as complete words.

Therefore `search` returns `True` exactly when at least one added word matches the query pattern.

## Complexity

Let:

```text
m = length of the word or query
```

For `addWord`:

| Metric | Value | Why |
|---|---|---|
| Time | `O(m)` | One Trie edge per character |
| Space | `O(m)` | May create one node per character |

For `search`:

| Case | Time | Why |
|---|---|---|
| No wildcard | `O(m)` | Follow one path |
| With wildcards | Up to `O(26^m)` worst case | `.` may branch into many children |

In practice, Trie depth is limited by word length, and branching is constrained by stored words.

Space for the whole dictionary is:

```text
O(total number of characters inserted)
```

## Implementation

```python
class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_word = False

class WordDictionary:

    def __init__(self):
        self.root = TrieNode()

    def addWord(self, word: str) -> None:
        node = self.root

        for ch in word:
            if ch not in node.children:
                node.children[ch] = TrieNode()

            node = node.children[ch]

        node.is_word = True

    def search(self, word: str) -> bool:
        def dfs(index: int, node: TrieNode) -> bool:
            if index == len(word):
                return node.is_word

            ch = word[index]

            if ch == ".":
                for child in node.children.values():
                    if dfs(index + 1, child):
                        return True

                return False

            if ch not in node.children:
                return False

            return dfs(index + 1, node.children[ch])

        return dfs(0, self.root)
```

## Code Explanation

The Trie starts with an empty root node:

```python
self.root = TrieNode()
```

Adding a word walks through the Trie:

```python
for ch in word:
```

If the character path does not exist, create it:

```python
if ch not in node.children:
    node.children[ch] = TrieNode()
```

After inserting every character, mark the final node:

```python
node.is_word = True
```

For search, define DFS:

```python
def dfs(index: int, node: TrieNode) -> bool:
```

If all query characters have been consumed:

```python
if index == len(word):
    return node.is_word
```

This returns `True` only for a complete inserted word.

For wildcard:

```python
if ch == ".":
```

try every child:

```python
for child in node.children.values():
    if dfs(index + 1, child):
        return True
```

If no branch works:

```python
return False
```

For a normal character, the path must exist:

```python
if ch not in node.children:
    return False
```

Then continue with the matching child:

```python
return dfs(index + 1, node.children[ch])
```

## Iterative Exact Search Is Not Enough

A normal Trie lookup would work for queries without dots:

```python
def search_exact(self, word: str) -> bool:
    node = self.root

    for ch in word:
        if ch not in node.children:
            return False

        node = node.children[ch]

    return node.is_word
```

But this cannot handle:

```python
"b.."
```

because each dot needs branching.

That is why DFS is needed.

## Testing

```python
def run_tests():
    wd = WordDictionary()

    wd.addWord("bad")
    wd.addWord("dad")
    wd.addWord("mad")

    assert wd.search("pad") is False
    assert wd.search("bad") is True
    assert wd.search(".ad") is True
    assert wd.search("b..") is True
    assert wd.search("ba") is False
    assert wd.search("...") is True
    assert wd.search("....") is False

    wd.addWord("a")
    assert wd.search(".") is True
    assert wd.search("a") is True
    assert wd.search("b") is False

    print("all tests passed")

run_tests()
```

| Test | Why |
|---|---|
| `"pad"` | Missing exact word |
| `"bad"` | Exact word exists |
| `".ad"` | Wildcard at first character |
| `"b.."` | Multiple trailing wildcards |
| `"ba"` | Prefix should not count as full word |
| `"..."` | Full wildcard query of length 3 |
| `"...."` | Wildcard length must match word length |
| `"."` after adding `"a"` | Single-character wildcard |