Trie (Prefix Tree)

1. Implement Trie Medium

Problem

Build a class with three methods. Insert(word) stores a word. Search(word) returns whether that exact word was stored. StartsWith(prefix) returns whether any stored word begins with prefix.

Approach

• Template A wrapped in a class. The root node stands for the empty prefix.
• Search and StartsWith share one private helper that walks a string and returns the node, or null.
• The only difference between them: Search also needs the end flag on the last node. The property pattern is { IsEnd: true } checks “not null and flagged” in one test.

Solution

/// <summary>A trie node: children by letter, plus an end-of-word flag.</summary>
public sealed class CharNode
{
    // Children: next letter -> child node.
    public Dictionary<char, CharNode> Children { get; } = [];

    // IsEnd: true when a stored word stops at this node.
    public bool IsEnd { get; set; }
}

/// <summary>Prefix tree with insert, exact search and prefix search.
/// Each method costs O(L) for a string of length L.</summary>
public sealed class Trie
{
    // The root holds no letter. It stands for the empty prefix "".
    private readonly CharNode _root = new();

    /// <summary>Store a word.</summary>
    /// <param name="word">The word to add.</param>
    /// <example><c>trie.Insert("apple")</c> then <c>trie.Search("apple")</c> is true.
    /// </example>
    public void Insert(string word)
    {
        var node = _root;
        // Invariant: node spells the letters of word read so far.
        foreach (char ch in word)
        {
            // Create the child on first use. Shared prefixes reuse it later.
            if (!node.Children.TryGetValue(ch, out var child))
            {
                child = new CharNode();
                node.Children[ch] = child;
            }
            node = child;                   // step down one letter
        }
        node.IsEnd = true;                  // a word stops here
    }

    /// <summary>Node reached by spelling text from the root, or null.</summary>
    private CharNode? Find(string text)
    {
        var node = _root;
        // Invariant: node spells the letters of text read so far.
        foreach (char ch in text)
        {
            // Missing child: no stored word has this prefix.
            if (!node.Children.TryGetValue(ch, out var child))
                return null;
            node = child;                   // step down one letter
        }
        return node;
    }

    /// <summary>Whether this exact word was inserted.</summary>
    /// <param name="word">The exact word to look for.</param>
    /// <returns>True only if word was stored, not just a longer word starting with it.
    /// </returns>
    /// <example>After <c>Insert("apple")</c>, <c>Search("app")</c> is false.</example>
    public bool Search(string word)
    {
        // The path must exist AND end on a flagged node.
        return Find(word) is { IsEnd: true };
    }

    /// <summary>Whether any stored word begins with prefix.</summary>
    /// <param name="prefix">The prefix to look for.</param>
    /// <returns>True if the path for prefix exists.</returns>
    /// <example>After <c>Insert("apple")</c>, <c>StartsWith("app")</c> is true.</example>
    public bool StartsWith(string prefix)
    {
        // The path existing is enough. No end flag needed.
        return Find(prefix) is not null;
    }
}

Walkthrough

• Insert("apple"): creates 5 nodes, a p p l e. Flags the e node.
• Search("app"): walks a p p. The node exists but is not flagged. false.
• StartsWith("app"): same walk, the node exists. true.
• Insert("app"): walks the 3 existing nodes, creates nothing, flags the second p.
• Search("app"): now flagged. true.

Reading the figure. Each column is the same trie at a later moment. Amber nodes are the path the call walks. Green ringed nodes have IsEnd set. In the middle column the walk succeeds but the last node has no flag, so Search says no. On the right, Insert("app") creates nothing and only sets the flag.

Edge cases to raise

• Empty string: Insert("") flags the root. StartsWith("") is always true. Ask whether empty words can occur.
• A null word: with nullable reference types on, the signature says string, not string?. Say you would add ArgumentNullException.ThrowIfNull(word) in production code.
• Inserting the same word twice: harmless. The second walk only sets the flag again.
• Delete: unflag the end node, then remove nodes bottom-up that have no children and no flag. A common follow-up.
• Counting words with a prefix: store a counter on each node and add 1 on every insert that passes through it.

2. Design Add and Search Words Medium

Problem

Build a class with AddWord(word) and Search(pattern). The search pattern may contain ., which matches any single letter. Return whether any added word matches the whole pattern.

Approach

• Store words in a trie, exactly as in Problem 1.
• For a normal letter, follow one child, as before.
• For a ., try every child. That turns the walk into a DFS. Return true as soon as one branch matches.
• At the end of the pattern, the match counts only if the node is flagged as a word end.
• A plain foreach with an early return beats LINQ Any here. It allocates no closure and reads the same.

Solution

/// <summary>A trie node for wildcard search.</summary>
public sealed class WildNode
{
    // Children: next letter -> child node.
    public Dictionary<char, WildNode> Children { get; } = [];

    // IsEnd: true when an added word stops at this node.
    public bool IsEnd { get; set; }
}

/// <summary>Word store whose search treats '.' as any single letter.</summary>
public sealed class WordDictionary
{
    // The root stands for the empty prefix "".
    private readonly WildNode _root = new();

    /// <summary>Store a word.</summary>
    /// <param name="word">Letters only, no wildcards.</param>
    /// <example><c>words.AddWord("bad")</c> then <c>words.Search(".ad")</c> is true.
    /// </example>
    public void AddWord(string word)
    {
        var node = _root;
        // Invariant: node spells the letters of word read so far.
        foreach (char ch in word)
        {
            // Create the child on first use.
            if (!node.Children.TryGetValue(ch, out var child))
            {
                child = new WildNode();
                node.Children[ch] = child;
            }
            node = child;                   // step down one letter
        }
        node.IsEnd = true;                  // a word stops here
    }

    /// <summary>Whether some stored word matches the pattern in full.</summary>
    /// <param name="pattern">Letters and '.', where '.' matches any one letter.</param>
    /// <returns>True if at least one stored word matches.</returns>
    /// <example>With "bad", "dad", "mad" stored, <c>Search("b..")</c> is true and
    /// <c>Search("b.")</c> is false.</example>
    public bool Search(string pattern)
    {
        // 0: start matching at the first symbol, from the root.
        return Match(_root, pattern, 0);
    }

    /// <summary>Can the subtree under node match pattern[i..]?</summary>
    private static bool Match(WildNode node, string pattern, int i)
    {
        // i == pattern.Length: every symbol matched. A word must end here.
        if (i == pattern.Length)
            return node.IsEnd;

        char ch = pattern[i];
        if (ch == '.')
        {
            // '.': any one letter, so try every child.
            // child is one letter some stored word uses at this depth.
            foreach (var child in node.Children.Values)
            {
                // i + 1: the next symbol. Return at the first branch that matches.
                if (Match(child, pattern, i + 1))
                    return true;
            }
            return false;
        }

        // A plain letter: only one child can match it.
        // i + 1: move on to the next symbol of the pattern.
        return node.Children.TryGetValue(ch, out var next) && Match(next, pattern, i + 1);
    }
}

Walkthrough

Stored: bad, dad, mad. Search .ad:

• Symbol 0 is .. Try children b, d, m in turn.
• Under b: symbol 1 a exists. Symbol 2 d exists.
• i == 3, the end of the pattern. The d node is flagged. The loop returns true without trying d or m.
• b. reaches the end at the a node, which is not flagged. false.

Reading the figure. The violet letters on top are the pattern, one column per symbol. The dot could follow b, d or m. Green is the branch that was tried and matched to a flagged node. Grey dashed branches were never visited, because the loop returned on the first true. Dictionary order is not guaranteed, so in a real run the first child tried might be d or m. The answer is the same.

Edge cases to raise

• A pattern of only dots, such as ...: matches any stored word of length 3.
• Pattern longer than every word: the walk runs out of children and returns false.
• Many dots near the front are the worst case, since each one fans out. Mention the bound.
• Recursion depth equals the pattern length. The default stack is about 1 MB, which holds thousands of frames. Fine for words, worth a sentence for very long strings.

3. Word Search II Hard

Problem

Given a grid of letters and a list of words, return every word that can be spelled by a path of adjacent cells (up, down, left, right). A path may not use the same cell twice.

Approach

• The naive way runs a backtracking search once per word. With many words that repeats the same grid paths over and over.
• Put all words in a trie. Run one DFS from each cell, moving down the trie as you move across the grid. This is Template B.
• Prune as soon as the letters so far are no word’s prefix.
• Store each full word on its end node. A match is then one field read.
• Clear a word once found, so it is reported once. Then cut off trie leaves that have nothing left to find. Later searches skip them.
• The board is a jagged char[][]. It works with collection expressions, and each row is a plain array you can change in place.

Solution

/// <summary>A trie node that stores the whole word at its end.</summary>
public sealed class GridNode
{
    // Children: next letter -> child node.
    public Dictionary<char, GridNode> Children { get; } = [];

    // Word: the full word ending here, or null if no word ends here.
    // Storing the word, not a flag, means the DFS never rebuilds the string.
    public string? Word { get; set; }
}

public static class WordSearchII
{
    // The 4 neighbours as (row step, col step): down, up, right, left.
    // 1 and -1 are one step. 0 means no move on that axis.
    private static readonly (int Dr, int Dc)[] Steps = [(1, 0), (-1, 0), (0, 1), (0, -1)];

    // '#': marks a used cell. No word contains it, so the trie never has a '#' child.
    private const char Used = '#';

    /// <summary>Every word from words that can be traced on the board.</summary>
    /// <param name="board">Grid of single letters. It is changed during the search and
    /// restored before returning.</param>
    /// <param name="words">Candidate words.</param>
    /// <returns>The words found, sorted in ordinal order, each listed once.</returns>
    /// <example><c>FindWords(grid, ["oath", "pea", "eat", "rain"])</c> returns
    /// <c>["eat", "oath"]</c> for the 4 x 4 example grid.</example>
    public static List<string> FindWords(char[][] board, string[] words)
    {
        // Empty grid, or a grid with an empty first row: nothing can be spelled.
        // 0: no rows, or no columns.
        if (board.Length == 0 || board[0].Length == 0)
            return [];

        // Build one trie holding every word.
        var root = new GridNode();
        foreach (string word in words)
        {
            var node = root;
            // Invariant: node spells the letters of word read so far.
            foreach (char ch in word)
            {
                if (!node.Children.TryGetValue(ch, out var child))
                {
                    child = new GridNode();
                    node.Children[ch] = child;
                }
                node = child;                 // step down one letter
            }
            node.Word = word;                 // the end node remembers the word
        }

        var found = new List<string>();

        // Try every cell as the first letter.
        // Invariant: found holds every word that starts at a cell already tried.
        for (int r = 0; r < board.Length; r++)
            for (int c = 0; c < board[r].Length; c++)
                Dfs(board, r, c, root, found);

        // Ordinal: plain char-code order, the same on every machine and culture.
        found.Sort(StringComparer.Ordinal);
        return found;
    }

    /// <summary>Extend the path into cell (r, c), one level below parent.</summary>
    private static void Dfs(char[][] board, int r, int c, GridNode parent, List<string> found)
    {
        char ch = board[r][c];
        // No child: no word has this prefix. Also catches Used, a cell on the path.
        if (!parent.Children.TryGetValue(ch, out var node))
            return;

        // A word ends here. Report it, then clear it so it is reported once.
        if (node.Word is not null)
        {
            found.Add(node.Word);
            node.Word = null;                 // null: this word is done
        }

        board[r][c] = Used;                   // mark used so the path cannot reuse it

        // (dr, dc) is one of the 4 neighbour steps.
        foreach (var (dr, dc) in Steps)
        {
            int nr = r + dr, nc = c + dc;
            // 0 <= nr < rows and 0 <= nc < cols: stay inside the grid.
            if (nr >= 0 && nr < board.Length && nc >= 0 && nc < board[nr].Length)
                Dfs(board, nr, nc, node, found);
        }

        board[r][c] = ch;                     // backtrack: give the cell back

        // Prune: a leaf with no word left can never match again. Cut it off
        // so later starts do not walk into it. 0: no children left.
        if (node.Children.Count == 0 && node.Word is null)
            parent.Children.Remove(ch);
    }
}

Walkthrough

Words oath, pea, eat, rain on the grid in the example:

• The trie root has children o, p, e, r.
• Cell (0, 0) is o. The DFS follows o → a → t → h through (0, 1), (1, 1), (2, 1). It finds oath, clears it, and prunes the now empty h leaf, then t, a, o on the way back.
• Cell (0, 1) is a. No root child a, so it stops in one step. Most cells end this way.
• Cell (1, 3) is e. The DFS follows e → a → t through (1, 2), (1, 1). It finds eat.
• pea has no p on the grid. rain has r at (2, 3) but no a next to it. Result: ["eat", "oath"].

Reading the figure. On the left, green cells and arrows trace oath. Violet traces eat, which reuses the same t cell. On the right is the trie of all four words. Ringed nodes are words found. Dashed nodes are never reached, because the grid has no next letter to match. Every other start cell fails at the root in one step.

L is the longest word. The first step has 4 directions, then 3, since you never step back onto the cell you came from. Pruning makes real runs far faster than this bound.

Edge cases to raise

• Duplicate words in the input: they share one end node, so each is reported once.
• A word that is a prefix of another, such as eat and eats: the first is reported and the DFS keeps going for the second. The node is only pruned when it has no children left.
• One-cell grid: works. The neighbour loop finds no valid cell.
• The board is changed during the search and put back. Say so, or clone each row if the caller must not see changes.
• Why '#' is safe: no word contains it, so TryGetValue('#', ...) always fails. Ask if the alphabet could include it.
• Sorting: StringComparer.Ordinal sorts by char code. The default comparer is culture-aware and can order some strings differently.

4. Replace Words Medium

Problem

Given a dictionary of roots and a sentence, replace every word with the shortest root that is a prefix of it. Words with no matching root stay as they are.

Approach

• Put every root in a trie, with the end flag on.
• For each word, walk the trie letter by letter. The first flagged node you hit is the shortest root. Stop there.
• If a letter has no child, or the word runs out, no root matches. Keep the word.
• Each word costs at most its own length, however many roots there are.
• Strings are immutable in C#. Build the output with one StringBuilder, not repeated +.

Solution

/// <summary>A trie node for dictionary roots.</summary>
public sealed class RootNode
{
    // Children: next letter -> child node.
    public Dictionary<char, RootNode> Children { get; } = [];

    // IsEnd: true when a root stops at this node.
    public bool IsEnd { get; set; }
}

public static class ReplaceWords
{
    /// <summary>Replace each word with the shortest dictionary root it starts with.</summary>
    /// <param name="dictionary">Root words.</param>
    /// <param name="sentence">Words separated by spaces.</param>
    /// <returns>The sentence with every word replaced by its shortest root, if any.
    /// </returns>
    /// <example><c>Replace(["cat", "bat", "rat"], "the cattle was rattled")</c> returns
    /// <c>"the cat was rat"</c>.</example>
    public static string Replace(string[] dictionary, string sentence)
    {
        // Build the trie of roots.
        var root = new RootNode();
        foreach (string stem in dictionary)
        {
            var node = root;
            // Invariant: node spells the letters of stem read so far.
            foreach (char ch in stem)
            {
                if (!node.Children.TryGetValue(ch, out var child))
                {
                    child = new RootNode();
                    node.Children[ch] = child;
                }
                node = child;                 // step down one letter
            }
            node.IsEnd = true;                // a root stops here
        }

        // RemoveEmptyEntries: runs of spaces do not make empty words.
        string[] words = sentence.Split(' ', StringSplitOptions.RemoveEmptyEntries);
        var sb = new System.Text.StringBuilder();
        // w is the index of the next word. Invariant: sb holds words[0..w) rewritten.
        for (int w = 0; w < words.Length; w++)
        {
            // 0: no space before the first word.
            if (w > 0)
                sb.Append(' ');
            sb.Append(ShortestRoot(root, words[w]));
        }
        return sb.ToString();
    }

    /// <summary>The shortest root that prefixes word, or word itself.</summary>
    private static string ShortestRoot(RootNode root, string word)
    {
        var node = root;
        // i is the index of the next letter.
        // Invariant: no root is a prefix of word[..i], or we would have returned.
        for (int i = 0; i < word.Length; i++)
        {
            // No child: no root continues this way. Keep the word.
            if (!node.Children.TryGetValue(word[i], out var child))
                return word;
            node = child;                     // step down one letter
            // First flagged node on the walk: the shortest matching root.
            if (node.IsEnd)
                return word[..(i + 1)];       // + 1: range end is exclusive, keep word[i]
        }
        // The word ran out first: it is a prefix of a root, not the reverse.
        return word;
    }
}

Walkthrough

Roots cat, bat, rat. Sentence the cattle was rattled:

• the: root has no t child. Kept.
• cattle: walks c a t. The t node is flagged after 3 letters, so return word[..3], which is cat.
• was: no w child. Kept.
• rattled: walks r a t, flagged. Becomes rat.

Reading the figure. The trie holds the roots. Amber nodes are the paths that cattle and rattled walk. Each walk stops at the first green ringed node, so the rest of the word is never read. On the right, green results were replaced. Grey ones had no matching first letter and stay as they are.

Edge cases to raise

• Two roots where one prefixes the other, such as a and aa: the walk stops at the first flag, so the shorter root wins.
• A word shorter than every root it begins: it runs out first and is kept.
• Empty dictionary: every word is kept.
• Extra spaces: StringSplitOptions.RemoveEmptyEntries drops them, so the output has single spaces. Ask if spacing must be kept.