What signals in a problem statement indicate the Prefix tree basics sub-pattern?

"implement a trie with insert, search, startsWith"; "replace each word with its shortest root"; "suggest at most three products after each typed character"

Prefix tree basics (Trie Sub-pattern)

Q: What makes Prefix tree basics different from other sub-patterns?

**Implement Trie** is the template; the trap is `search` returning true for a word that is only a prefix. **Replace Words** walks each sentence word and stops at the **first** end flag, so the shortest root wins. **Search Suggestions** walks one level per typed letter; storing the 3 smallest words at each node during insert (products sorted first) makes each answer O(1). Once the walk falls off the trie, every later prefix has no suggestions.

Build a trie of words, then answer prefix questions by walking it: exists, shortest prefix, or suggestions while typing.

Signals in the problem statement

›
"implement a trie with insert, search, startsWith"
›
"replace each word with its shortest root"
›
"suggest at most three products after each typed character"

What makes it different

Implement Trie is the template; the trap is search returning true for a word that is only a prefix. Replace Words walks each sentence word and stops at the first end flag, so the shortest root wins. Search Suggestions walks one level per typed letter; storing the 3 smallest words at each node during insert (products sorted first) makes each answer O(1). Once the walk falls off the trie, every later prefix has no suggestions.

Questions

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

1
Implement Trie (Prefix Tree)
Basic Anchor·LeetCode #208
WalkthroughMedium
2
Replace Words
Medium·LeetCode #648
WalkthroughMedium
3
Search Suggestions System
Interview-Level·LeetCode #1268
WalkthroughMedium

Template

trie-template.cpp

// Prefix tree: one node per prefix; children indexed by letter.
struct TrieNode {
    TrieNode* child[26] = {};
    bool isEnd = false;                       // a whole word ends here (not just a prefix)
};

class Trie {
    TrieNode* root = new TrieNode();

    // Walks the path for s; returns the last node, or nullptr if the path breaks.
    TrieNode* walk(const string& s) {
        TrieNode* cur = root;
        for (char c : s) {
            cur = cur->child[c - 'a'];
            if (!cur) return nullptr;
        }
        return cur;
    }

public:
    void insert(const string& word) {
        TrieNode* cur = root;
        for (char c : word) {
            if (!cur->child[c - 'a']) cur->child[c - 'a'] = new TrieNode();
            cur = cur->child[c - 'a'];
        }
        cur->isEnd = true;
    }
    bool search(const string& word) { TrieNode* n = walk(word); return n && n->isEnd; }
    bool startsWith(const string& prefix) { return walk(prefix) != nullptr; }
};

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)?

Trie overview Trie + DFS search