Follow Trie Edges

Checking your account…

Loading the interactive Practice workspace.If it does not appear, the problem and learning material remain readable, but browser execution is unavailable.Reload Practice workspace

Problem

Implement trie_prefix_match_lengths(words, queries). Build a trie from words. For each query, return the number of leading characters that can be followed from the trie root before an edge is missing. A full word marker is not required.

Starter code

def trie_prefix_match_lengths(words, queries):
    pass

Test cases

shared-prefixes

{
  "args": [
    [
      "cat",
      "car",
      "dog"
    ],
    [
      "cart",
      "cap",
      "do",
      "z"
    ]
  ]
}

Expected: [3,2,2,0]

empty-query

{
  "args": [
    [
      "abc"
    ],
    [
      ""
    ]
  ]
}

Expected: [0]

Wizard outline

Step 1: Create the empty trie root
Return zero matched characters for every query when no word inserts an edge. One root dictionary is the stable entry point shared by all later word and query walks.
Step 2: Insert and read one edge
Create nested dictionaries for word characters and test one-character queries against root. A single edge proves both insertion and lookup direction before longer shared paths are traversed.
Step 3: Walk the longest existing prefix
Reset node to root for each query, follow existing edges in order, and stop at the first missing character. The complete walk reuses shared prefixes while preserving one independent match count per query.

Footguns and prerequisites

Checking only complete words returns zero for valid prefixes that are not stored as standalone words.
Reusing the terminal node from one query instead of restarting at the root corrupts later matches.
trees and graphs

Reviewed references

Python Mapping Types — dict

Prepared Interview Problems

Implement Trie(opens in a new tab)
Follow Trie Edges isolates after matching k characters, node is the trie node reached by exactly query[:k]; the first missing edge ends the match. That focused state discipline is required when implementing implement trie as a complete Interview Problem.
Map Sum Pairs(opens in a new tab)
Follow Trie Edges isolates after matching k characters, node is the trie node reached by exactly query[:k]; the first missing edge ends the match. That focused state discipline is required when implementing map sum pairs as a complete Interview Problem.
Wildcard Word Dictionary(opens in a new tab)
Follow Trie Edges isolates after matching k characters, node is the trie node reached by exactly query[:k]; the first missing edge ends the match. That focused state discipline is required when implementing word dictionary wildcard as a complete Interview Problem.
Word Search II(opens in a new tab)
Follow Trie Edges isolates after matching k characters, node is the trie node reached by exactly query[:k]; the first missing edge ends the match. That focused state discipline is required when implementing word search two as a complete Interview Problem.

Recommended approach and implementation

A trie converts shared string prefixes into shared edges, so prefix traversal depends on query length rather than the number of stored words. After matching k characters, node is the trie node reached by exactly query[:k]; the first missing edge ends the match.

Why it works: Insertion creates an edge for every stored prefix. Query traversal follows exactly one edge per character, so the traversed count is the longest existing prefix; the first absent edge proves no longer prefix can match.

def trie_prefix_match_lengths(words, queries):
    root = {}
    for word in words:
        node = root
        for character in word:
            node = node.setdefault(character, {})
    lengths = []
    for query in queries:
        node = root
        matched = 0
        for character in query:
            if character not in node:
                break
            node = node[character]
            matched += 1
        lengths.append(matched)
    return lengths