Course4all

Add and Search Word

Expert Answer & Key Takeaways

A complete guide to understanding and implementing Trie.

Add and Search Word

Design a data structure that supports adding new words and finding if a string matches any previously added string, including wildcard character '.' matching.
Medium

Examples

Input: addWord("bad"), addWord("dad"), search(".ad")
Output: true, true, true
Approach 1

Level III: Trie + DFS (Optimal)

Intuition

Standard Trie implementation. When encountering '.', perform DFS to check all possible children of the current node.
⏱ Add: O(L), Search: O(26^L) worst case.💾 O(N * L * 26).

Detailed Dry Run

Search '.ad': Root -> dfs('.'). Try 'a'-'z'. 'b' exists. From 'b', dfs('ad') -> matches 'ad' and isEnd=true. Return true.
java
class WordDictionary {
    class Node { Node[] children = new Node[26]; boolean isEnd = false; }
    Node root = new Node();
    public void addWord(String w) { Node c=root; for(char x:w.toCharArray()) { int i=x-'a'; if(c.children[i]==null) c.children[i]=new Node(); c=c.children[i]; } c.isEnd=true; }
    public boolean search(String w) { return dfs(w, 0, root); }
    private boolean dfs(String w, int i, Node n) {
        if(n==null) return false; if(i==w.length()) return n.isEnd;
        char x=w.charAt(i);
        if(x=='.') { for(Node child:n.children) if(dfs(w, i+1, child)) return true; return false; }
        return dfs(w, i+1, n.children[x-'a']);
    }
}

Course4All Technical Board

Verified Expert

Senior Software Engineers & Algorithmic Experts

Our DSA content is authored and reviewed by engineers from top tech firms to ensure optimal time and space complexity analysis.

Pattern: 2026 Ready
Updated: Weekly
← Previous QuestionImplement Trie (Prefix Tree)
Next Question →Map Sum Pairs