🦄 Rooted Runes: Shortest Prefix Replacement

Difficulty: Intermediate Tags: trie, strings, prefix-matching, dictionary Series: CS 102: Problem Solving & Logic

Problem

In the ancient library, rooted runes hold the essence of longer words. Replace each word in a sentence with the shortest root that matches its prefix.

Given a list of roots (dictionary words) and a sentence, replace each word in the sentence with the shortest root that is a prefix of that word. If no root matches, keep the original word.

Real-World Application

Root-based word replacement appears in: - Text compression - replacing words with shorter roots to save space - Search engines - stemming algorithms for better search results - Natural language processing - morphological analysis and lemmatization - Autocorrect systems - suggesting corrections based on root words - Spell checkers - identifying word stems for validation - Information retrieval - improving keyword matching - Machine translation - normalizing words to their base forms

Input

data = {
    'roots': List[str],  # List of root words (dictionary)
    'sentence': str      # Sentence to process
}

Output

str  # Sentence with words replaced by shortest matching roots

Constraints

• 1 ≤ total length ≤ 100,000
• Lowercase letters a-z only
• Words separated by single spaces
• A root matches if it's a prefix of the word

Examples

Example 1: Basic Replacement

Input:

{
    'roots': ['cat', 'bat', 'rat'],
    'sentence': 'the cattle was rattled by the battery'
}

Output: 'the cat was rat by the bat'

Explanation: - 'the' - no matching root → keep 'the' - 'cattle' - matches root 'cat' → replace with 'cat' - 'was' - no matching root → keep 'was' - 'rattled' - matches root 'rat' → replace with 'rat' - 'by' - no matching root → keep 'by' - 'the' - no matching root → keep 'the' - 'battery' - matches root 'bat' → replace with 'bat'

Example 2: No Matches

Input:

{
    'roots': ['zzz'],
    'sentence': 'abc def'
}

Output: 'abc def'

Explanation: - No word starts with 'zzz' - All words remain unchanged

Example 3: Multiple Possible Roots (Shortest Wins)

Input:

{
    'roots': ['a', 'aa', 'aaa'],
    'sentence': 'aadsfasf aadsfa aaaa'
}

Output: 'a a a'

Explanation: - All three words start with 'a', 'aa', and 'aaa' - But we use the shortest root: 'a'

Example 4: Exact Match

Input:

{
    'roots': ['cat', 'dog'],
    'sentence': 'cat dog bird'
}

Output: 'cat dog bird'

Explanation: - 'cat' matches exactly → replace with 'cat' (no change) - 'dog' matches exactly → replace with 'dog' (no change) - 'bird' - no matching root → keep 'bird'

Example 5: Overlapping Roots

Input:

{
    'roots': ['catt', 'cat', 'bat', 'rat'],
    'sentence': 'the cattle was rattled by the battery'
}

Output: 'the cat was rat by the bat'

Explanation: - For 'cattle', both 'cat' and 'catt' are roots - Use shortest: 'cat'

Example 6: Root Longer Than Word

Input:

{
    'roots': ['hello'],
    'sentence': 'hi world'
}

Output: 'hi world'

Explanation: - 'hello' is not a prefix of 'hi' or 'world' - Keep both words unchanged

What You'll Learn

• Trie data structure for efficient prefix matching
• String tokenization and reconstruction
• Finding shortest matching prefix
• When to use Trie vs simpler approaches
• Handling multiple matching roots

Why This Matters

This problem demonstrates: - Classic Trie application - Efficient prefix matching at scale - String processing fundamentals - Trade-offs between data structure complexity and performance

Frequently appears in interviews at: Amazon, Google, Microsoft

Starter Code

def challenge_function(data):
    """
    Replace words in sentence with shortest matching root.

    Args:
        data: dict with keys:
            - 'roots' (List[str]): list of root words
            - 'sentence' (str): sentence to process

    Returns:
        str: sentence with words replaced by shortest roots
    """
    # Your implementation here
    pass