Trie-based String Problems

Before we start

Binary search trees store numbers and sort them by value. A trie stores strings and sorts them by prefix. If you understand a linked list (each node points to the next) and a dictionary (each node has up to 26 children), you already understand the trie. By the end of this chapter you will be able to:

• Build a trie from scratch and insert/search words in O(L) per word.
• Explain why a trie beats a hash set for prefix queries.
• Use the trie skeleton to solve Word Search II (backtracking + trie) and Longest Common Prefix.

Picture this first (no code yet)

First, the slow way (so you feel the pain)

You have a dictionary of 100 000 words and want to check if any starts with the prefix "pre". With a list: scan all 100 000 words and check .startswith("pre") — O(N × L). For N = 100 000 and L = 10, that is 1 million character comparisons, repeated for every keystroke the user types. Autocomplete for a phone keyboard fires on every keypress — 8 million comparisons per second just for prefix checking. A trie does this in O(L) = 10 steps.

The turning point

root
├── a
│   └── p
│       ├── p  [END: "app"]
│       │   └── l
│       │       └── e  [END: "apple"]
│       └── t  [END: "apt"]
└── b
    └── a
        └── t  [END: "bat"]

The one idea to remember

Building a trie from scratch

class TrieNode:
    def __init__(self):
        self.children = {}       # char → TrieNode
        self.is_end   = False    # True if a complete word ends here

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()   # create node if missing
            node = node.children[ch]              # walk down
        node.is_end = True                        # mark end of word

    def search(self, word: str) -> bool:
        node = self.root
        for ch in word:
            if ch not in node.children:
                return False           # path doesn't exist
            node = node.children[ch]
        return node.is_end             # must land on a complete word, not just a prefix

    def startsWith(self, prefix: str) -> bool:
        node = self.root
        for ch in prefix:
            if ch not in node.children:
                return False
            node = node.children[ch]
        return True                    # any node reached = prefix exists

Key difference between search and startsWith:

• search("app") returns True only if "app" was inserted — checks is_end.
• startsWith("app") returns True if any inserted word starts with "app" — no is_end check.

Watch it happen, frame by frame

Insert "apple" and "app", then search.

Insert "apple":
root → create 'a' → create 'p' → create 'p' → create 'l' → create 'e'
Mark 'e' node: is_end = True

Insert "app":
root → 'a' exists → 'p' exists → 'p' exists (shared!)
Mark this 'p' node: is_end = True

Now the tree:
root
└── a
    └── p
        └── p  [is_end=True ← "app"]
            └── l
                └── e  [is_end=True ← "apple"]

search("apple"): walk a→p→p→l→e, is_end=True → True ✅
search("app"):   walk a→p→p, is_end=True → True ✅
search("ap"):    walk a→p, is_end=False → False ✅ (not an inserted word)
startsWith("ap"):walk a→p, return True → True ✅ (prefix exists)

Application 1 — Word Search II (LC #212)

Given a 2D grid of characters and a list of words, find all words from the list that appear in the grid (adjacent cells horizontally/vertically, no cell reuse).

Why trie + backtracking? Without a trie, for each word you'd do a full DFS — O(N × 4^L). With a trie, one DFS explores all words simultaneously — you follow the trie path as you walk the grid, and prune whenever the current path isn't a prefix of any word.

def findWords(board, words):
    root = TrieNode()
    for w in words:
        node = root
        for ch in w:
            if ch not in node.children:
                node.children[ch] = TrieNode()
            node = node.children[ch]
        node.is_end = w      # store the word itself (not just True) for easy retrieval

    rows, cols = len(board), len(board[0])
    result     = set()

    def dfs(r, c, node):
        ch = board[r][c]
        if ch not in node.children:
            return                      # prune: no word goes this way
        next_node = node.children[ch]
        if next_node.is_end:
            result.add(next_node.is_end)   # found a complete word
            next_node.is_end = False       # avoid duplicates

        board[r][c] = '#'              # mark visited
        for dr, dc in [(0,1),(0,-1),(1,0),(-1,0)]:
            nr, nc = r + dr, c + dc
            if 0 <= nr < rows and 0 <= nc < cols and board[nr][nc] != '#':
                dfs(nr, nc, next_node)
        board[r][c] = ch              # restore

    for r in range(rows):
        for c in range(cols):
            dfs(r, c, root)

    return list(result)

Why set is_end = False after finding a word? Once found, we don't want to add the same word again if another grid path leads to the same trie leaf. Clearing is_end prevents duplicates without removing the node (which could break other words sharing the prefix).

Application 2 — Longest Common Prefix (LC #14)

Find the longest prefix shared by all strings in a list.

def longestCommonPrefix(strs: list[str]) -> str:
    if not strs:
        return ""

    # Insert all strings into trie, then walk until branching point
    root = TrieNode()
    for s in strs:
        node = root
        for ch in s:
            if ch not in node.children:
                node.children[ch] = TrieNode()
            node = node.children[ch]
        node.is_end = True

    # Walk from root: keep going as long as exactly one child and not is_end
    prefix = []
    node   = root
    while len(node.children) == 1 and not node.is_end:
        ch   = next(iter(node.children))
        prefix.append(ch)
        node = node.children[ch]

    return "".join(prefix)

The walk stops when: a node has more than one child (strings diverge here), or a node is is_end (one of the strings ends here — the common prefix can't be longer).

O(N × L) to build, O(L) to walk — total O(N × L).

When a hash set is faster, when trie wins

Common traps

Complexity

Say it like a pro (interview one-liner)

"I'll use a trie — each node has a children map (char to node) and an is_end flag. Insertion walks the path character by character creating nodes as needed in O(L). Search checks the path and the is_end flag. Prefix search is the same without the is_end check. This gives O(L) per query regardless of dictionary size, which beats O(N×L) linear scan for prefix problems."

class TrieNode:
    def __init__(self):
        self.children = {}    # char → TrieNode
        self.is_end   = False

# insert:     walk + create nodes + set is_end = True at last
# search:     walk + return is_end at last (False if path missing)
# startsWith: walk + return True if path exists (ignore is_end)

Check yourself

Practice problems

This completes Chapter 3 — Strings (12 patterns). Next: Chapter 4 — Linked Lists, starting with Floyd's fast & slow pointer technique for cycle detection.