Trie Applications: Autocomplete, Word Break, and More

A Trie (prefix tree) is the go-to data structure when you need fast prefix lookups. While hash maps can check if a word exists in O(L) time (where L is word length), they cannot efficiently answer questions like “what words start with this prefix?” or “what is the closest match?” Tries answer these in O(L) time plus O(results) for enumeration. This post covers six real interview problems where a Trie shines.

The Trie building block

Every problem in this post uses the same Trie node structure. Here is the version we will build on:

class TrieNode:
    def __init__(self):
        self.children = {}      # char -> TrieNode
        self.is_end = False     # marks the end of a word
        self.word = None        # optional: store the full word at leaf

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word: str) -> None:
        node = self.root
        for ch in word:
            if ch not in node.children:
                node.children[ch] = TrieNode()
            node = node.children[ch]
        node.is_end = True
        node.word = word

    def search(self, word: str) -> bool:
        node = self._find(word)
        return node is not None and node.is_end

    def starts_with(self, prefix: str) -> bool:
        return self._find(prefix) is not None

    def _find(self, prefix: str) -> TrieNode:
        node = self.root
        for ch in prefix:
            if ch not in node.children:
                return None
            node = node.children[ch]
        return node

Time complexity for all operations: O(L) where L is the length of the word or prefix. Space complexity: O(N * L) where N is the number of words and L is the average word length.

Problem 1: Design Autocomplete System

LeetCode 642. Design a system that provides at most 3 suggestions for every character the user types. Among all matching sentences, return the top 3 sorted by frequency (then lexicographically).

Approach

Store all sentences in a Trie. At each node, maintain a list of (sentence, frequency) pairs or use DFS to collect all sentences under a prefix. For efficiency, we store sorted suggestions at each node.

class AutocompleteNode:
    def __init__(self):
        self.children = {}
        self.sentences = {}  # sentence -> frequency

class AutocompleteSystem:
    def __init__(self, sentences: list, times: list):
        self.root = AutocompleteNode()
        self.current_input = ""
        self.current_node = self.root
        self.dead = AutocompleteNode()  # fallback for no-match

        for sentence, time in zip(sentences, times):
            self._insert(sentence, time)

    def _insert(self, sentence: str, count: int) -> None:
        node = self.root
        for ch in sentence:
            if ch not in node.children:
                node.children[ch] = AutocompleteNode()
            node = node.children[ch]
            node.sentences[sentence] = node.sentences.get(sentence, 0) + count

    def input(self, c: str) -> list:
        if c == '#':
            # End of input — record the sentence
            self._insert(self.current_input, 1)
            self.current_input = ""
            self.current_node = self.root
            return []

        self.current_input += c

        # Navigate to the next node
        if c not in self.current_node.children:
            self.current_node = self.dead
            return []
        self.current_node = self.current_node.children[c]

        # Get top 3 suggestions
        items = self.current_node.sentences.items()
        # Sort by: -frequency (descending), then sentence (ascending)
        sorted_items = sorted(items, key=lambda x: (-x[1], x[0]))
        return [item[0] for item in sorted_items[:3]]

Usage

system = AutocompleteSystem(
    ["i love you", "island", "iroman", "i love leetcode"],
    [5, 3, 2, 2]
)

print(system.input('i'))   # ["i love you", "island", "i love leetcode"]
print(system.input(' '))   # ["i love you", "i love leetcode"]
print(system.input('a'))   # []
print(system.input('#'))   # [] — records "i a"

Time complexity: O(L) for navigating + O(S log S) for sorting suggestions, where S is the number of matching sentences. Space complexity: O(N * L) for the Trie, where N is total sentences.

Problem 2: Search Suggestions System

LeetCode 1268. Given an array of products and a search word, return lists of at most 3 suggestions after each character of the search word is typed. Suggestions must have the search word as a prefix and be lexicographically sorted.

Approach

Insert all products into a Trie. At each node, keep a sorted list of up to 3 words. When a new word passes through a node, insert it in sorted order and trim to 3.

class SuggestionNode:
    def __init__(self):
        self.children = {}
        self.suggestions = []  # sorted list, max 3

class SearchSuggestionSystem:
    def __init__(self):
        self.root = SuggestionNode()

    def insert(self, word: str) -> None:
        node = self.root
        for ch in word:
            if ch not in node.children:
                node.children[ch] = SuggestionNode()
            node = node.children[ch]
            # Insert in sorted order, keep at most 3
            self._insert_sorted(node.suggestions, word)

    def _insert_sorted(self, lst: list, word: str) -> None:
        # Binary search for insertion point
        lo, hi = 0, len(lst)
        while lo {'<'} hi:
            mid = (lo + hi) // 2
            if lst[mid] {'<'} word:
                lo = mid + 1
            else:
                hi = mid
        lst.insert(lo, word)
        if len(lst) > 3:
            lst.pop()

    def search(self, search_word: str) -> list:
        result = []
        node = self.root
        for ch in search_word:
            if node and ch in node.children:
                node = node.children[ch]
                result.append(list(node.suggestions))
            else:
                node = None
                result.append([])
        return result


def suggested_products(products: list, search_word: str) -> list:
    system = SearchSuggestionSystem()
    for product in products:
        system.insert(product)
    return system.search(search_word)

Example

products = ["mobile", "mouse", "moneypot", "monitor", "mousepad"]
search_word = "mouse"

print(suggested_products(products, search_word))
# [
#   ["mobile", "moneypot", "monitor"],   # prefix "m"
#   ["mobile", "moneypot", "monitor"],   # prefix "mo"
#   ["mouse", "mousepad"],               # prefix "mou"
#   ["mouse", "mousepad"],               # prefix "mous"
#   ["mouse", "mousepad"]                # prefix "mouse"
# ]

Time complexity: O(N * L * log 3) for building + O(L) for searching, where N is the number of products and L is max product length. Effectively O(N * L). Space complexity: O(N * L) for the Trie.

Alternative: Sort + Binary Search

A simpler approach that does not use a Trie:

def suggested_products_binary(products: list, search_word: str) -> list:
    import bisect

    products.sort()
    result = []
    prefix = ""

    for ch in search_word:
        prefix += ch
        idx = bisect.bisect_left(products, prefix)
        suggestions = []
        for i in range(idx, min(idx + 3, len(products))):
            if products[i].startswith(prefix):
                suggestions.append(products[i])
            else:
                break
        result.append(suggestions)

    return result

Time: O(N log N) for sorting + O(L * log N) for binary searches.

Problem 3: Word Break with Trie

LeetCode 139. Given a string s and a dictionary of words, determine if s can be segmented into a space-separated sequence of dictionary words.

Why Trie helps

The classic solution uses DP with a hash set. A Trie offers a subtle advantage: when checking all dictionary words starting at position i, a Trie lets you walk character by character and stop early when no word has the current prefix.

def word_break(s: str, word_dict: list) -> bool:
    # Build Trie from dictionary
    root = TrieNode()
    for word in word_dict:
        node = root
        for ch in word:
            if ch not in node.children:
                node.children[ch] = TrieNode()
            node = node.children[ch]
        node.is_end = True

    n = len(s)
    dp = [False] * (n + 1)
    dp[0] = True  # empty string is always valid

    for i in range(n):
        if not dp[i]:
            continue
        # Walk the Trie from position i
        node = root
        for j in range(i, n):
            ch = s[j]
            if ch not in node.children:
                break  # no dictionary word has this prefix
            node = node.children[ch]
            if node.is_end:
                dp[j + 1] = True

    return dp[n]

Walkthrough

For s = "leetcode", word_dict = ["leet", "code"]:

• dp[0] = True.
• From i=0: walk l-e-e-t — is_end at t, so dp[4] = True.
• From i=4: walk c-o-d-e — is_end at e, so dp[8] = True.
• dp[8] is True, so the answer is True.

Trie vs hash set comparison

Approach	Time per position	Total Time
Hash set	O(n * L) — check each substring	O(n^2 * L)
Trie	O(L_max) — walk until no match	O(n * L_max)

Where L_max is the maximum word length. The Trie approach is faster when the dictionary has many words with shared prefixes.

Time complexity: O(n * L_max) where n is the string length. Space complexity: O(W * L) for the Trie where W is the number of words.

Problem 4: Longest Word in Dictionary

LeetCode 720. Given a list of words, return the longest word that can be built one character at a time by other words in the list. If there is a tie, return the lexicographically smallest one.

Approach

Insert all words into a Trie. Then do a DFS/BFS to find the longest word where every prefix is also a complete word (is_end is True at every step).

def longest_word(words: list) -> str:
    # Build Trie
    root = TrieNode()
    root.is_end = True  # empty string is a valid base

    for word in words:
        node = root
        for ch in word:
            if ch not in node.children:
                node.children[ch] = TrieNode()
            node = node.children[ch]
        node.is_end = True
        node.word = word

    # BFS to find longest word with all prefixes present
    from collections import deque
    queue = deque([root])
    result = ""

    while queue:
        node = queue.popleft()
        for ch in sorted(node.children.keys()):
            child = node.children[ch]
            if child.is_end:
                word = child.word
                # Update result: longer word wins, or lexicographically smaller
                if len(word) > len(result) or (
                    len(word) == len(result) and word {'<'} result
                ):
                    result = word
                queue.append(child)

    return result

Example

For words = ["a", "banana", "app", "appl", "ap", "apply", "apple"]:

• Build Trie with all words.
• BFS finds: a -> ap -> app -> appl -> apple and apply.
• Both "apple" and "apply" have length 5. "apple" < "apply" lexicographically.
• Answer: "apple".

Time complexity: O(N * L) for Trie construction + O(N * L) for BFS = O(N * L). Space complexity: O(N * L) for the Trie.

Problem 5: Replace Words

LeetCode 648. Given a dictionary of roots and a sentence, replace each word in the sentence with the shortest root that is a prefix of the word.

Approach

Build a Trie from the roots. For each word in the sentence, walk the Trie and return the first complete root found.

def replace_words(dictionary: list, sentence: str) -> str:
    # Build Trie from roots
    root = TrieNode()
    for word in dictionary:
        node = root
        for ch in word:
            if ch not in node.children:
                node.children[ch] = TrieNode()
            node = node.children[ch]
        node.is_end = True

    def find_root(word: str) -> str:
        node = root
        for i, ch in enumerate(word):
            if ch not in node.children:
                return word  # no root found
            node = node.children[ch]
            if node.is_end:
                return word[:i + 1]  # shortest root
        return word

    words = sentence.split()
    return " ".join(find_root(w) for w in words)

Example

dictionary = ["cat", "bat", "rat"]
sentence = "the cattle was rattled by the battery"

print(replace_words(dictionary, sentence))
# "the cat was rat by the bat"

• "cattle" -> walk c-a-t, is_end=True at t, return "cat".
• "rattled" -> walk r-a-t, is_end=True at t, return "rat".
• "battery" -> walk b-a-t, is_end=True at t, return "bat".
• "the", "was", "by" -> no matching root, keep original.

Time complexity: O(D * L + S * L) where D is dictionary size, S is number of words in sentence, L is max word length. Space complexity: O(D * L) for the Trie.

Problem 6: Implement Magic Dictionary

LeetCode 676. Design a data structure that is initialized with a list of distinct words and can search for a target word with exactly one character changed.

Approach

Build a Trie and use DFS with a “mismatch budget” of 1. When searching, traverse the Trie. If the current character matches, continue normally. If it does not match, try all other children but decrement the budget. If the budget goes below 0, prune that branch.

class MagicDictionary:
    def __init__(self):
        self.root = TrieNode()

    def build_dict(self, dictionary: list) -> None:
        for word in dictionary:
            node = self.root
            for ch in word:
                if ch not in node.children:
                    node.children[ch] = TrieNode()
                node = node.children[ch]
            node.is_end = True

    def search(self, search_word: str) -> bool:
        return self._dfs(self.root, search_word, 0, 0)

    def _dfs(self, node, word, index, mismatches):
        if index == len(word):
            return node.is_end and mismatches == 1

        ch = word[index]
        for child_ch, child_node in node.children.items():
            new_mismatches = mismatches + (0 if child_ch == ch else 1)
            if new_mismatches {'<'}= 1:
                if self._dfs(child_node, word, index + 1, new_mismatches):
                    return True

        return False

Example

md = MagicDictionary()
md.build_dict(["hello", "leetcode"])

print(md.search("hello"))    # False — 0 mismatches, need exactly 1
print(md.search("hhllo"))    # True  — change 'h' at index 1 to 'e'
print(md.search("hell"))     # False — different length, no match
print(md.search("leetcoded"))# False — different length

Why exactly 1 mismatch?

The problem says “exactly one character modified.” This means:

• mismatches == 0 at the end: not valid (word is in the dictionary but not modified).
• mismatches == 1 at the end: valid.
• mismatches >= 2 at any point: prune.

Time complexity: O(L * 26) per search in the worst case (trying all 26 children at the mismatch position). Space complexity: O(N * L) for the Trie.

When to use a Trie vs a Hash Map

Use Case	Trie	Hash Map
Exact word lookup	O(L)	O(L) — tie
Prefix search	O(L) + O(results)	O(N * L) — scan all
Autocomplete	Natural fit	Awkward
Fuzzy matching	DFS with budget	Generate all variants
Memory with shared prefixes	Efficient	Wasteful
Simple word set membership	Overkill	Preferred

Rule of thumb: If the problem mentions “prefix”, “autocomplete”, “starts with”, or “one character off”, think Trie. If it is just “does this word exist”, use a hash set.

Trie performance tuning

Use arrays instead of dicts for speed

When the character set is small (e.g., lowercase English), replace the dictionary with a fixed-size array:

class FastTrieNode:
    def __init__(self):
        self.children = [None] * 26
        self.is_end = False

    def get(self, ch):
        return self.children[ord(ch) - ord('a')]

    def put(self, ch, node):
        self.children[ord(ch) - ord('a')] = node

This trades space for speed — array indexing is faster than dictionary hashing.

Compressed Trie (Radix Tree)

If many nodes have only one child, compress chains into single edges. For example, if the only word starting with "un" is "unfortunately", store "unfortunately" as a single edge instead of 13 nodes.

This optimization matters for memory-heavy applications but rarely comes up in interviews.

Practice problems

1. LeetCode 208 — Implement Trie (Prefix Tree)
2. LeetCode 211 — Design Add and Search Words Data Structure
3. LeetCode 642 — Design Autocomplete System
4. LeetCode 1268 — Search Suggestions System
5. LeetCode 139 — Word Break
6. LeetCode 720 — Longest Word in Dictionary
7. LeetCode 648 — Replace Words
8. LeetCode 676 — Implement Magic Dictionary
9. LeetCode 212 — Word Search II
10. LeetCode 1065 — Index Pairs of a String

Final thoughts

The Trie is one of those data structures that seems niche until you realize how many interview problems it unlocks. The core implementation — insert, search, starts_with — is only about 25 lines of code. Once you have that memorized, every problem becomes about adding a small twist: DFS for autocomplete, a mismatch counter for fuzzy matching, early termination for root replacement.

Build the Trie from scratch in every practice session until it is second nature. In an interview, you want to write the Trie code in under two minutes and spend the remaining time on the actual problem logic.