What signals in a problem statement indicate the Trie + DFS search sub-pattern?

"`.` can match any letter"; "find all words from the dictionary on the board"; many words, one search space

Trie + DFS search (Trie Sub-pattern)

Q: What makes Trie + DFS search different from other sub-patterns?

**Add and Search Words** branches only at `.`: it tries all children, and still needs `isEnd` at the end. **Word Search II** inserts every word, then runs **one** DFS per board cell that moves through the trie with it. When a word is found, clear its end flag so it isn't reported twice, and restore each board cell when backtracking. Running a separate search for every word is just the brute force again.

When a query can branch (wildcards, a board of letters), run a DFS that walks the trie at the same time and stops as soon as no stored word continues the path.

Signals in the problem statement

›
". can match any letter"
›
"find all words from the dictionary on the board"
›
many words, one search space

What makes it different

Add and Search Words branches only at .: it tries all children, and still needs isEnd at the end. Word Search II inserts every word, then runs one DFS per board cell that moves through the trie with it. When a word is found, clear its end flag so it isn't reported twice, and restore each board cell when backtracking. Running a separate search for every word is just the brute force again.

Questions

ordered from “learn the idea” to “recognise it without help”

1
Design Add and Search Words Data Structure
Basic Anchor·LeetCode #211
WalkthroughMedium
2
Word Search II
Interview-Level·LeetCode #212
WalkthroughHard

Template

trie-dfs-template.cpp

// Trie + DFS: when one letter can branch (a wildcard, a grid neighbour),
// try every child, but only along paths that exist in the trie.
// Here: search with '.' matching any one letter (LC 211).
struct TrieNode {
    TrieNode* child[26] = {};
    bool isEnd = false;
};

bool match(TrieNode* node, const string& pat, int i) {
    if (!node) return false;                  // the path broke: no word continues this way
    if (i == (int)pat.size()) return node->isEnd;
    if (pat[i] != '.') return match(node->child[pat[i] - 'a'], pat, i + 1);
    for (TrieNode* next : node->child)        // '.': any existing child may continue the match
        if (next && match(next, pat, i + 1)) return true;
    return false;
}

Remember this · Trie

Trigger

Many words + prefix search, autocomplete, word dictionary with wildcards, maximum XOR.

Think

Do many queries share prefixes that I keep re-checking?

Key question

What does each node store (children, end-of-word, count)?

Prefix tree basics Bitwise trie