Design Add and Search Words Data Structure (LC 211)

Pattern: Trie + DFS (Wildcard)
Difficulty: Medium
Key Concept: . matches any single letter — at a . node, try all non-null children recursively; otherwise follow the single matching edge.

Problem Statement

Implement WordDictionary with:

• addWord(word) — store word
• search(word) — return true if any stored word matches. . matches any one letter.

Example

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

---

1. Algorithm & Pseudocode

Brute force

1. Keep ArrayList<String> words.
2. addWord → append O(1).
3. search → for each stored word, if lengths differ skip; else compare char-by-char treating . as wildcard — O(N × L) per search.

Pseudocode

addWord(w): words.add(w)

search(s):
    for w in words:
        if match(w, s): return true
    return false

match(w, s):
    if len differs: false
    for i:
        if s[i] == '.' or s[i] == w[i]: continue
        else: false
    return true

Optimal

1. Trie as in LC 208.
2. search DFS: dfs(node, index):
   • If index == len return node.end.
   • If s[index] != '.' go to that child if exists.
   • Else for each child c in node.children if c != null, recurse dfs(c, index+1); if any true, return true.

Pseudocode

function dfs(node, i):
    if i == len(s): return node.end
    ch = s[i]
    if ch != '.':
        child = node.next[ch]
        return child != null && dfs(child, i + 1)
    for each letter k in 0..25:
        if node.next[k] != null && dfs(node.next[k], i + 1):
            return true
    return false

---

2. Step-by-Step Analysis (Beginner-Friendly)

• Trie prunes: shared prefixes mean you do not rescan whole strings from scratch for every query.
• . branching explodes to up to 26 recursive tries at that position — still better than scanning all words when dictionary is large and shares structure.
• Why DFS not BFS: You need to explore alternate branches at . with backtracking naturally expressed as recursion.

---

3. The Dry Run

Stored: bad, dad, mad — shared structure:

         root
    /     |     \
   b      d      m
   |      |      |
   a      a      a
   |      |      |
   d*     d*     d*

Query search("b..")

Step	node	index	char	Action
1	root	0	b	go to b child
2	b	1	.	try a (only child)
3	a	2	.	try d
4	d	3	end	end==true → true

ASCII (path for b..)

root --b--> a --d*
        ^     ^
      idx0   idx1 '.' then idx2 '.' lands on d*

---

4. Java Solution

Brute Force

import java.util.*;

class WordDictionaryBrute {
    private final List<String> words = new ArrayList<>();

    public WordDictionaryBrute() {}

    public void addWord(String word) {
        words.add(word);
    }

    // Time per search: O(N * L), Space: O(N * L)
    public boolean search(String word) {
        for (String w : words) {
            if (w.length() != word.length()) continue;
            if (match(w, word)) return true;
        }
        return false;
    }

    private boolean match(String w, String s) {
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c != '.' && c != w.charAt(i)) return false;
        }
        return true;
    }
}

Optimal

class WordDictionary {
    private static class Node {
        Node[] next = new Node[26];
        boolean end;
    }

    private final Node root = new Node();

    public WordDictionary() {}

    public void addWord(String word) {
        Node cur = root;
        for (int i = 0; i < word.length(); i++) {
            int idx = word.charAt(i) - 'a';
            if (cur.next[idx] == null) cur.next[idx] = new Node();
            cur = cur.next[idx];
        }
        cur.end = true;
    }

    // Time: O(26^k * L) worst with k dots; Space: O(L) recursion
    public boolean search(String word) {
        return dfs(root, word, 0);
    }

    private boolean dfs(Node node, String s, int i) {
        if (node == null) return false;
        if (i == s.length()) return node.end;
        char ch = s.charAt(i);
        if (ch != '.') {
            return dfs(node.next[ch - 'a'], s, i + 1);
        }
        for (int k = 0; k < 26; k++) {
            if (node.next[k] != null && dfs(node.next[k], s, i + 1)) return true;
        }
        return false;
    }
}

---

5. The “Java vs. Others” Edge

• Worst-case . spam can approach 26^d branches; interviewers care you know this trade-off.
• WordDictionary naming matches LeetCode; not Trie class name here.
• Iterative DFS needs an explicit stack structure for backtracking — recursion is clearer in Java.

---

6. Complexity Summary

Approach	addWord	search	Space
Brute list	O(1)	O(N·L)	O(N·L)
Trie + DFS	O(L)	O(26^d·L) worst, O(L) best	O(total chars) trie

d = number of . characters in the query.