Build a data structure that can store words and search them, but with a twist: the search function must support the dot character . which can match any single letter.

Example:

addWord("bad")
addWord("dad")
addWord("mad")

search("pad") → false  
search("bad") → true  
search(".ad") → true  
search("b..") → true

---

Problem Requirements

You must implement a class with two methods:

addWord(word)

Stores a word in the data structure.

search(pattern)

Returns true if:

• the exact word exists, OR
• the pattern matches using . wildcard characters

Constraints to keep in mind:

• Words consist of lowercase English letters
• The number of operations can be large (thousands to tens of thousands)
• Efficiency matters — you cannot search linearly through all words every time

---

Why a Simple Approach Fails

A naïve strategy might be:

• Store all words in a list
• During search, compare pattern to every stored word

This becomes too slow because:

• Each search becomes O(n * m)
  n = number of stored words
  m = word length
• With thousands of operations, this times out

So we need something faster.

---

Logic in Simple English (Core Idea)

To solve this efficiently, we use a Trie, a special tree for storing words character by character.

Why a Trie works:

1. Words share prefixes, so storage is efficient.
2. Searching letter-by-letter is fast.
3. When encountering ., we can explore all possible child paths.
4. This makes wildcard searching manageable without scanning all words.

So the idea becomes:

• Store each word in a Trie
• For search:
  • If the current character is a letter, follow that child path
  • If the character is ., try all children recursively
  • If we reach the end of the pattern and the node marks the end of a valid word, return true
  • Otherwise return false

This gives fast add and flexible search.

---

Step-by-Step Solution Approach

For addWord(word):

1. Start at root node
2. For each character:
   • If child doesn’t exist, create it
   • Move into that child
3. Mark the final node as end-of-word

For search(pattern):

1. Use depth-first search (DFS)
2. At each index:
   • If normal letter: follow matching child
   • If ., recursively try all children
3. If index reaches end and node is end-of-word → return true
4. If no path matches → return false

---

Java Implementation

class WordDictionary {

    private static class TrieNode {
        TrieNode[] children = new TrieNode[26];
        boolean isEndOfWord = false;
    }

    private final TrieNode root;

    public WordDictionary() {
        root = new TrieNode();
    }

    public void addWord(String word) {
        TrieNode current = root;
        for (char c : word.toCharArray()) {
            int index = c - 'a';
            if (current.children[index] == null) {
                current.children[index] = new TrieNode();
            }
            current = current.children[index];
        }
        current.isEndOfWord = true;
    }

    public boolean search(String word) {
        return dfsSearch(word, 0, root);
    }

    private boolean dfsSearch(String word, int index, TrieNode node) {
        if (index == word.length()) {
            return node.isEndOfWord;
        }

        char c = word.charAt(index);

        if (c == '.') {
            for (TrieNode child : node.children) {
                if (child != null && dfsSearch(word, index + 1, child)) {
                    return true;
                }
            }
            return false;
        } else {
            int idx = c - 'a';
            TrieNode next = node.children[idx];
            return next != null && dfsSearch(word, index + 1, next);
        }
    }
}

---

Dry Run Example

Let’s walk through this sequence:

addWord("bad")
addWord("dad")
addWord("mad")
search(".ad")

Adding “bad”

• Insert b → a → d
• Mark final node as end-of-word

Adding “dad”

• Insert d → a → d
• Mark final node

Adding “mad”

• Insert m → a → d
• Mark final node

Searching “.ad”

Index 0: .

• Explore all children: b, d, m

Branch 1: b-path
Index 1: ‘a’ → matches
Index 2: ‘d’ → matches
End reached → node is end-of-word → return true

Since one path succeeds, final result = true

---

Time and Space Complexity

addWord

Time: O(L)
Space: O(L) worst case
L = word length

search

Worst-case Time: O(26^L) when many dots
Typical Time: O(L) for exact match, much faster than brute force

Space

Trie uses up to 26 branches per node

---

Common Mistakes and How to Avoid Them

❌ Storing words in a list → too slow
✅ Use Trie

❌ Returning false when encountering . too early
✅ Try all child nodes

❌ Forgetting to check end-of-word flag
✅ A full pattern match must end on a marked node

❌ Assuming all words have same length
✅ Subarrays vary; search must respect length