🦄 Rootweave Trie: Dictionary Roots

Difficulty: Intermediate Tags: trie, data-structures, prefix-tree, dictionary Series: CS 102: Problem Solving & Logic

Problem

In the mystical forest, the Rootweave holds all knowledge in a tree of interconnected roots. Implement a Trie (prefix tree) to efficiently store and search for words.

Implement a Trie data structure that supports three operations: - insert(word) - Add a word to the dictionary - search(word) - Return true if the exact word exists - startsWith(prefix) - Return true if any word starts with this prefix

You'll be given a list of operations and should return the results of all search and startsWith operations in order.

Real-World Application

Tries are fundamental in: - Autocomplete systems - Google search, IDE code completion - Spell checkers - suggesting corrections, detecting typos - IP routing - longest prefix matching in routers - Genome sequencing - pattern matching in DNA sequences - Dictionary implementations - efficient word lookup - Search engines - indexing and prefix queries - T9 predictive text - phone keyboard word suggestions - Command line shells - tab completion

Input

data = {
    'ops': List[List[str]]  # List of operations
}

Each operation is one of: - ['insert', word] - Insert word into Trie - ['search', word] - Check if exact word exists - ['startsWith', prefix] - Check if any word has this prefix

Output

List[bool]  # Results for search and startsWith operations only

Constraints

• Total operations ≤ 100,000
• Words contain only lowercase letters a-z
• 1 ≤ word length ≤ 50

Examples

Example 1: Basic Trie Operations

Input:

{
    'ops': [
        ['insert', 'unicorn'],
        ['search', 'uni'],
        ['startsWith', 'uni'],
        ['search', 'unicorn']
    ]
}

Output: [False, True, True]

Explanation: - insert 'unicorn' - Add 'unicorn' to Trie (no output) - search 'uni' - 'uni' is not a complete word → False - startsWith 'uni' - 'unicorn' starts with 'uni' → True - search 'unicorn' - 'unicorn' exists as complete word → True

Example 2: Multiple Words

Input:

{
    'ops': [
        ['insert', 'a'],
        ['insert', 'ab'],
        ['search', 'ab'],
        ['startsWith', 'abc']
    ]
}

Output: [True, False]

Explanation: - insert 'a' - Add 'a' (no output) - insert 'ab' - Add 'ab' (no output) - search 'ab' - 'ab' exists → True - startsWith 'abc' - No word starts with 'abc' → False

Example 3: Prefix vs Exact Match

Input:

{
    'ops': [
        ['insert', 'apple'],
        ['search', 'app'],
        ['startsWith', 'app'],
        ['insert', 'app'],
        ['search', 'app']
    ]
}

Output: [False, True, True]

Explanation: - After inserting 'apple', 'app' is a prefix but not a word → search False - 'app' is a valid prefix → startsWith True - After inserting 'app', it becomes a word → search True

Example 4: No Matches

Input:

{
    'ops': [
        ['insert', 'cat'],
        ['search', 'dog'],
        ['startsWith', 'dog']
    ]
}

Output: [False, False]

Explanation: - Only 'cat' is inserted - 'dog' doesn't exist → False - No word starts with 'dog' → False

What You'll Learn

• Implementing tree-like data structures
• Understanding prefix matching
• Using nested dictionaries or node classes
• Marking terminal nodes (word endings)
• Difference between prefix and exact match

Why This Matters

Trie is a classic data structure tested in: - FAANG interviews (Google, Amazon, Facebook, etc.) - Systems design discussions - Performance optimization problems - String processing challenges

Understanding Tries demonstrates mastery of tree structures and efficient string operations.

Starter Code

def challenge_function(data):
    """
    Implement a Trie with insert, search, and startsWith operations.

    Args:
        data: dict with key:
            - 'ops' (List[List[str]]): list of operations
              Each op is ['insert', word] or ['search', word] or ['startsWith', prefix]

    Returns:
        List[bool]: results for search and startsWith operations only
    """
    # Your implementation here
    pass