Data Structures19 sections · 729 units
Open in Course

Prefix Search

The trie advantage

Checking if any word starts with a prefix is simpler. Just verify the path exists:

def startsWith(prefix):
    node = root
    for char in prefix:
        if char not in node.children:
            return false
        node = node.children[char]
    return true

No need to check isEndOfWord. If the path exists, some word has this prefix (possibly the prefix itself, possibly a longer word).

To get all words with a given prefix:

1.1. Go to the prefix's node

2.2. DFS from there, collecting all paths that end at isEndOfWord = true

That's why tries power autocomplete. Finding all completions of a prefix is a single subtree traversal.