Search prefixes with a trie
Insert lowercase words into a trie and determine whether any stored word starts with a requested prefix.
Course progress
Problem 86 of 100
Example → approach → runnable solution
Worked example
See the problem in action
Trace a concrete input through to the verified result.
Example input
words = ["code", "coder", "coil"]; prefixes = ["co", "cat"]
Expected output
True False
What is happening?
All inserted words begin through the trie path c -> o, so co succeeds. No child a follows c, so cat fails.
Solution strategy
Build the right mental model
Store one child map per character. Prefix search succeeds when every requested character can be followed from the root.
Core concepts
trie · strings
Complexity
Insert and prefix search take O(k) time for a k-character input; stored nodes use O(total characters).
Runnable solution
Learn from working code
Compare languages, copy the code, or open it in the compiler.
Complete C# solution for trie-prefix-search
using System;
using System.Collections.Generic;
class Program
{
class TrieNode
{
public Dictionary<char, TrieNode> Children = new Dictionary<char, TrieNode>();
}
class Trie
{
private readonly TrieNode root = new TrieNode();
public void Insert(string word)
{
TrieNode node = root;
foreach (char symbol in word)
{
TrieNode next;
if (!node.Children.TryGetValue(symbol, out next))
{
next = new TrieNode();
node.Children[symbol] = next;
}
node = next;
}
}
public bool StartsWith(string prefix)
{
TrieNode node = root;
foreach (char symbol in prefix)
if (!node.Children.TryGetValue(symbol, out node)) return false;
return true;
}
}
static void Main()
{
var trie = new Trie();
trie.Insert("code");
trie.Insert("coder");
trie.Insert("coil");
Console.WriteLine(trie.StartsWith("co"));
Console.WriteLine(trie.StartsWith("cat"));
}
}Knowledge check
Questions students often ask
What is the main idea behind search prefixes with a trie?
Store one child map per character. Prefix search succeeds when every requested character can be followed from the root.
What is the time and space complexity of this solution?
Insert and prefix search take O(k) time for a k-character input; stored nodes use O(total characters).
Do all language tabs solve the same problem?
Yes. Every program uses the same example and produces the verified output shown on this page. The syntax and a few language-specific data structures differ.