Trie: Pattern, Template & 49 LeetCode Problems

What the trie pattern is

A trie stores a set of strings as a tree in which each edge is one character and each path from the root spells a prefix, so words sharing a prefix share the nodes that spell it. Lookup and insertion cost the length of the word and nothing else — the size of the dictionary does not appear in the complexity, which is why a trie beats a hash set for every question about prefixes rather than whole words. The node needs exactly two things: a map from character to child, and a flag saying a word ends here, because "car" being present must be distinguishable from "car" merely being a prefix of "cart". Two extensions cover most of the harder problems: storing a count or the best word at each node answers autocomplete queries without walking the subtree, and pairing a trie with a backtracking search over a grid prunes whole regions the moment the prefix stops existing, which is what makes a word-search-over-a-dictionary tractable.

When to use it

Queries are about prefixes: autocomplete, "does any word start with…", longest common prefix.
A large dictionary is searched many times and repeated prefix work is the bottleneck.
A backtracking search over a grid or a string needs to be pruned by a word list.
Wildcards must be matched inside words, where a hash set cannot help at all.

The trie template in Python

The shape, not a solution to any one problem. Adapt the condition and the summary being maintained; the skeleton stays the same across the 49 problems listed below.

PythonTrie template

class Trie:
    def __init__(self):
        self.children = {}
        self.is_word = False       # "car" present vs. "car" merely a prefix of "cart"

    def insert(self, word):
        node = self
        for char in word:
            node = node.children.setdefault(char, Trie())
        node.is_word = True

    def find(self, prefix):
        """The node reached by prefix, or None. is_word tells you if it is a word."""
        node = self
        for char in prefix:
            node = node.children.get(char)
            if node is None:
                return None
        return node

Complexity characteristics

Time: O(L) per insert or lookup, where L is the length of the word
Auxiliary space: O(total characters stored)

The cost of a lookup is the length of the key and nothing else — the number of words already stored does not appear in it, which is the property a hash set cannot match for prefix queries. The space is one node per distinct prefix, so a dictionary with heavy prefix sharing costs far less than the sum of its word lengths and one with none costs exactly that sum. Pairing a trie with a grid search prunes the moment a prefix stops existing, which changes the observed cost by orders of magnitude without changing the worst case.

Eyes only

Meet the trie problem you did not practise.

In the live round, Stealth Interview reads the problem off your screen, returns a working solution with a step-by-step explanation and its time and space complexity, and transcribes what the interviewer says. It's a desktop app for macOS and Windows, invisible to screen sharing.

Get Stealth Interview See pricing

90%Subscription

python

Please analyze this context and help me answer the question or solve the problem.

Technical interview · 45 minsolution.pyShared editor · Python 3Longest substring without repeatsMediumGiven a string s, return the length of the longest contiguous substring in which every character is unique.s = "abcabcbb"
→ 31def length_of_longest_substring(s: str) -> int:2 last_seen = {}3 left = best = 04 for right, ch in enumerate(s):5 if ch in last_seen and last_seen[ch] >= left:

python

def length_of_longest_substring(s: str) -> int:    last_seen = {}                    # char -> index    left = best = 0    for right, ch in enumerate(s):        if ch in last_seen and last_seen[ch] >= left:            left = last_seen[ch] + 1  # jump past it        last_seen[ch] = right        best = max(best, right - left + 1)    return best    last_seen = {}                    # char -> index

Approach

At each index r, the window's left edge is:

left r = max (left r -1, last[s r] + 1)

Time O(n): each character enters and leaves the window once.
Space O(min(n, k)): k is the size of the character set.

Type your message...

GPT-6.1 Terra

90%Subscription

python

Please analyze this context and help me answer the question or solve the problem.

Technical interview · 45 minsolution.pyShared editor · Python 3Longest substring without repeatsMediumGiven a string s, return the length of the longest contiguous substring in which every character is unique.s = "abcabcbb"
→ 31def length_of_longest_substring(s: str) -> int:2 last_seen = {}3 left = best = 04 for right, ch in enumerate(s):5 if ch in last_seen and last_seen[ch] >= left:

python

def length_of_longest_substring(s: str) -> int:    last_seen = {}                    # char -> index    left = best = 0    for right, ch in enumerate(s):        if ch in last_seen and last_seen[ch] >= left:            left = last_seen[ch] + 1  # jump past it        last_seen[ch] = right        best = max(best, right - left + 1)    return best    last_seen = {}                    # char -> index

Approach

At each index r, the window's left edge is:

left r = max (left r -1, last[s r] + 1)

Time O(n): each character enters and leaves the window once.
Space O(min(n, k)): k is the size of the character set.

Type your message...

GPT-6.1 TerraClear chat

QuitEscHide+QCapture+PCrop+OSubmit+EnterPress to get answerLeft/Right+Up/Down+

90%Subscription

python

Please analyze this context and help me answer the question or solve the problem.

Technical interview · 45 minsolution.pyShared editor · Python 3Longest substring without repeatsMediumGiven a string s, return the length of the longest contiguous substring in which every character is unique.s = "abcabcbb"
→ 31def length_of_longest_substring(s: str) -> int:2 last_seen = {}3 left = best = 04 for right, ch in enumerate(s):5 if ch in last_seen and last_seen[ch] >= left:

python

def length_of_longest_substring(s: str) -> int:    last_seen = {}                    # char -> index    left = best = 0    for right, ch in enumerate(s):        if ch in last_seen and last_seen[ch] >= left:            left = last_seen[ch] + 1  # jump past it        last_seen[ch] = right        best = max(best, right - left + 1)    return best    last_seen = {}                    # char -> index

Approach

At each index r, the window's left edge is:

left r = max (left r -1, last[s r] + 1)

Time O(n): each character enters and leaves the window once.
Space O(min(n, k)): k is the size of the character set.

Type your message...

GPT-6.1 TerraClear chat

Primary display

QuitEscHide+QCapture+PCrop+OSubmit+EnterPress to get answerLeft/Right+Up/Down+

All 49 trie LeetCode problems

Every problem in the library the trie pattern applies to, grouped by LeetCode's own difficulty rating. 36 of the 49 carry a complete Python solution with a worked example and complexity analysis; the rest are listed for completeness, with the LeetCode Premium ones marked.

Easy (3)

Easy problems
No.	Problem	Topics
0014	Longest Common Prefix	Trie, Array, String
1065	Index Pairs of a StringPremium	Trie, Array, String +1
2932	Maximum Strong Pair XOR I	Bit Manipulation, Trie, Array +2

Medium (24)

Medium problems
No.	Problem	Topics
0139	Word Break	Trie, Memoization, Array +3
0208	Implement Trie (Prefix Tree)	Design, Trie, Hash Table +1
0211	Design Add and Search Words Data Structure	Depth-First Search, Design, Trie +1
0386	Lexicographical Numbers	Depth-First Search, Trie
0421	Maximum XOR of Two Numbers in an Array	Bit Manipulation, Trie, Array +1
0648	Replace Words	Trie, Array, Hash Table +1
0676	Implement Magic Dictionary	Depth-First Search, Design, Trie +2
0677	Map Sum Pairs	Design, Trie, Hash Table +1
0692	Top K Frequent Words	Trie, Array, Hash Table +5
0720	Longest Word in Dictionary	Trie, Array, Hash Table +2
1268	Search Suggestions System	Trie, Array, String +3
0616	Add Bold Tag in StringPremium	Trie, Array, Hash Table +2
0758	Bold Words in StringPremium	Trie, Array, Hash Table +2
0792	Number of Matching Subsequences	Trie, Array, Hash Table +4
0820	Short Encoding of Words	Trie, Array, Hash Table +1
1023	Camelcase Matching	Trie, Array, Two Pointers +2
1166	Design File SystemPremium	Design, Trie, Hash Table +1
1233	Remove Sub-Folders from the Filesystem	Depth-First Search, Trie, Array +1
1698	Number of Distinct Substrings in a StringPremium	Trie, String, Suffix Array +2
1804	Implement Trie II (Prefix Tree)Premium	Design, Trie, Hash Table +1
1858	Longest Word With All PrefixesPremium	Depth-First Search, Trie, Array +1
2261	K Divisible Elements Subarrays	Trie, Array, Hash Table +3
2452	Words Within Two Edits of Dictionary	Trie, Array, String
2707	Extra Characters in a String	Trie, Array, Hash Table +2

Hard (22)

Hard problems
No.	Problem	Topics
0140	Word Break II	Trie, Memoization, Array +4
0212	Word Search II	Trie, Array, String +2
0336	Palindrome Pairs	Trie, Array, Hash Table +1
0440	K-th Smallest in Lexicographical Order	Trie
0472	Concatenated Words	Depth-First Search, Trie, Array +3
0745	Prefix and Suffix Search	Design, Trie, Array +2
0425	Word SquaresPremium	Trie, Array, String +1
0527	Word AbbreviationPremium	Greedy, Trie, Array +2
0588	Design In-Memory File SystemPremium	Design, Trie, Hash Table +2
0642	Design Search Autocomplete SystemPremium	Depth-First Search, Design, Trie +4
1032	Stream of Characters	Design, Trie, Array +2
1178	Number of Valid Words for Each Puzzle	Bit Manipulation, Trie, Array +2
1316	Distinct Echo Substrings	Trie, String, Hash Function +1
1707	Maximum XOR With an Element From Array	Bit Manipulation, Trie, Array
1803	Count Pairs With XOR in a Range	Bit Manipulation, Trie, Array
1938	Maximum Genetic Difference Query	Bit Manipulation, Depth-First Search, Trie +2
1948	Delete Duplicate Folders in System	Trie, Array, Hash Table +2
2227	Encrypt and Decrypt Strings	Design, Trie, Array +2
2416	Sum of Prefix Scores of Strings	Trie, Array, String +1
2479	Maximum XOR of Two Non-Overlapping SubtreesPremium	Tree, Depth-First Search, Graph +1
2935	Maximum Strong Pair XOR II	Bit Manipulation, Trie, Array +2
2977	Minimum Cost to Convert String II	Graph, Trie, Array +3

Problems sit in more than one pattern more often than not, and the overlap is where the interesting follow-up questions live.

Trie pattern FAQ

What is the trie pattern?

A trie stores a set of strings as a tree in which each edge is one character and each path from the root spells a prefix, so words sharing a prefix share the nodes that spell it.

How many LeetCode problems use the trie pattern?

This page lists 49 LeetCode problems that the trie pattern applies to: 3 Easy, 24 Medium and 22 Hard. 36 of them carry a complete Python solution with complexity analysis.

What is the time complexity of the trie pattern?

O(L) per insert or lookup, where L is the length of the word time and O(total characters stored) space. The cost of a lookup is the length of the key and nothing else — the number of words already stored does not appear in it, which is the property a hash set cannot match for prefix queries. The space is one node per distinct prefix, so a dictionary with heavy prefix sharing costs far less than the sum of its word lengths and one with none costs exactly that sum. Pairing a trie with a grid search prunes the moment a prefix stops existing, which changes the observed cost by orders of magnitude without changing the worst case.

When should I use the trie pattern in an interview?

Queries are about prefixes: autocomplete, "does any word start with…", longest common prefix. A large dictionary is searched many times and repeated prefix work is the bottleneck.

Which trie problem should I start with?

LeetCode 14. Longest Common Prefix is the lowest-numbered Easy problem on this page, which makes it the usual starting point: the technique is visible without the problem's own complications getting in the way.

What patterns are related to trie?

Hash Map, Backtracking, Tree Traversal, Depth-First Search. Problems frequently sit in more than one of these, and the overlap is where the interesting follow-up questions come from.

More ways in: all 22 patterns, the curated study lists, or the full problem list.

What the trie pattern is

When to use it

The trie template in Python

Complexity characteristics

Meet the trie problem you did not practise.

Approach

Approach

Approach

All 49 trie LeetCode problems

Easy (3)3

Medium (24)24

Hard (22)22

Related patterns

Trie pattern FAQ

What is the trie pattern?

How many LeetCode problems use the trie pattern?

What is the time complexity of the trie pattern?

When should I use the trie pattern in an interview?

Which trie problem should I start with?

What patterns are related to trie?

Easy (3)

Medium (24)

Hard (22)