DSA From Zero to Job-ReadyLesson 23 of 28

Lessons

1 · Foundations (Think Like a Programmer)

2 · Data Structures and Recursion

3 · Core Algorithms and Reusable Patterns

4 · Advanced Interview Topics

5 · From Practice to Job-Ready

Lesson 23 of 28

Lesson 23 · Advanced Interview Topics

Tries and Prefix-Based Search

A trie stores words so that shared prefixes share nodes, making insert, exact search and prefix search take time proportional to the word length. Build one in Java, compare array and map nodes, and use it for autocomplete, wildcards and shortest-prefix replacement.

By Karthikeyan A19 min readTechnology

For

Learners who know trees, strings and hashing and want to handle prefix queries efficiently, with honest guidance on when a trie is worth it.

Level

Advanced

Before you start

Articles 6, 9 and 11: strings, hash maps and trees. A trie is a tree whose edges are characters.

On this page

Key takeaways

A trie (prefix tree) stores strings as paths from a root, one character per edge. Words that share a prefix share the nodes for that prefix.
Insert, exact search and prefix search each take O(L) time, where L is the length of the word, regardless of how many words are stored.
Each node keeps a way to find its children (an array of 26 for lowercase letters, or a HashMap for any characters) and a flag that marks the end of a word.
Tries shine for autocomplete, prefix counting and pruning searches. For a plain yes-or-no lookup a HashSet is simpler, and a sorted set is often enough for prefix queries.
Tries can use a lot of memory. State the alphabet you assume, and choose the node representation to match it.

Type "pre" into a search box and a list of suggestions appears: "prefix", "present", "prepare". The program did not read through every word in its dictionary to find the ones that begin with "pre". With a million words, that would be far too slow to do on every keystroke.

Instead, it keeps the words in a structure built for exactly this question: a trie (pronounced "try", from retrieval), also called a prefix tree. In a trie, words that start the same way share the same path, so "pre" is stored once, and every word beginning with "pre" hangs off that one spot. Finding the suggestions is as simple as walking down the path "p, r, e" and then collecting what is below.

Tries are not as common in everyday code as arrays and hash maps, but they come up in interviews because they are a good test of whether you can design a small data structure cleanly.

What you will learn

What a trie is, and how words share prefixes.
Two ways to represent a node, and their trade-offs.
How to implement insert, search, prefix search and autocomplete in Java.
The complexity in terms of word length, and the memory cost.
When to use a trie, and when a simpler structure is better.

The idea

A trie is a tree where:

the root represents the empty prefix;
each edge is labelled with one character;
the path from the root to any node spells a prefix;
a node has a flag, isWord, that says "a stored word ends exactly here".

Here is a trie that stores the words cat, car, card, do and dog. A * marks a node where a word ends.

Code

(root) ├── c │    └── a │         ├── t*          "cat" │         └── r*          "car" │              └── d*     "card" └── d      └── o*               "do"           └── g*          "dog"

Look at what is shared. cat, car and card all begin with c-a, so those two nodes are stored once. car is also a prefix of card: the node for r is marked as a word (car) and also has a child (d). That is why the flag is needed: a node can be a word and a prefix of longer words. Similarly do is a word and a prefix of dog.

How the algorithms work

Insert a word. Start at the root. For each character: if the current node has no child for it, create one. Move to that child. After the last character, set isWord = true on the node you are standing on.

Search for an exact word. Walk down following the characters. If a child is missing at any point, the word is not there. If you reach the end of the word, check the isWord flag. (Reaching the node is not enough: ca leads to a node, but ca is not a stored word.)

Prefix search (startsWith). The same walk, but you do not need the flag: if you can follow all the characters, some word starts with this prefix. (This holds because every node in the trie lies on the path to at least one stored word.)

Autocomplete. Walk down the prefix. If you get stuck, there are no suggestions. Otherwise, from the node you reached, do a depth-first traversal that collects every word below it. If you visit children in alphabetical order, the suggestions come out sorted, which is a pleasant bonus.

Each of these does a constant amount of work per character, so for a word of length L, insert, search and startsWith take O(L) time. And that cost does not depend on how many words are stored: a trie of a million words answers a 5-letter query in about 5 steps.

Node representation

The one design decision is how a node finds its children. There are two common choices.

	Array of 26	`HashMap<Character, Node>`
Alphabet	Fixed: here, lowercase `a` to `z`	Anything: digits, symbols, mixed case
Child lookup	`children[c - 'a']`, very fast	A hash lookup, a bit slower
Memory per node	26 references, even if most are `null`	Only the children that exist, but each entry has overhead
Order of children	Alphabetical for free	Unordered (use a `TreeMap` for sorted)
Best for	Lowercase English words, speed	Larger or unknown alphabets, sparse tries

For most interview problems, the array version with lowercase letters is the expected answer. State the assumption out loud: "I will assume lowercase a to z".

Memory. A trie has at most one node per character stored plus the root, so up to (total characters + 1) nodes. With the array representation, every node reserves 26 slots, so the memory is about 26 × (number of nodes) references. For a dictionary of a few hundred thousand words, that is plenty. Prefix sharing reduces the number of nodes, but not as much as people expect for words that do not overlap.

A trie in Java

Java

// File: Main.javaimport java.util.ArrayList;import java.util.List;public class Main {    static class Trie {        private static class Node {            final Node[] children = new Node[26];            boolean isWord;        }        private final Node root = new Node();        private int nodeCount = 1;                       // the root        private static int indexOf(char c) {            if (c < 'a' || c > 'z') {                throw new IllegalArgumentException("only lowercase a-z is supported: " + c);            }            return c - 'a';        }        void insert(String word) {            Node node = root;            for (char c : word.toCharArray()) {                int i = indexOf(c);                if (node.children[i] == null) {                    node.children[i] = new Node();                    nodeCount++;                }                node = node.children[i];            }            node.isWord = true;        }        // Returns the node reached by following the prefix, or null if the path does not exist.        private Node find(String prefix) {            Node node = root;            for (char c : prefix.toCharArray()) {                node = node.children[indexOf(c)];                if (node == null) {                    return null;                }            }            return node;        }        boolean contains(String word) {            Node node = find(word);            return node != null && node.isWord;          // the node must exist AND end a word        }        boolean startsWith(String prefix) {            return find(prefix) != null;        }        // Up to limit words that start with prefix, in alphabetical order.        List<String> wordsWithPrefix(String prefix, int limit) {            List<String> result = new ArrayList<>();            Node start = find(prefix);            if (start != null) {                collect(start, new StringBuilder(prefix), result, limit);            }            return result;        }        private void collect(Node node, StringBuilder path, List<String> result, int limit) {            if (result.size() >= limit) {                return;            }            if (node.isWord) {                result.add(path.toString());            }            for (int i = 0; i < 26; i++) {               // alphabetical order                if (node.children[i] != null) {                    path.append((char) ('a' + i));                    collect(node.children[i], path, result, limit);                    path.deleteCharAt(path.length() - 1);   // backtrack                }            }        }        int nodes() {            return nodeCount;        }    }    public static void main(String[] args) {        Trie trie = new Trie();        for (String word : new String[] {"cat", "car", "card", "care", "dog", "do"}) {            trie.insert(word);        }        System.out.println("nodes including the root: " + trie.nodes());        System.out.println(trie.contains("car") + " " + trie.contains("ca") + " " + trie.contains("cards") + " " + trie.contains("do") + " " + trie.contains(""));        System.out.println(trie.startsWith("ca") + " " + trie.startsWith("cab") + " " + trie.startsWith("d") + " " + trie.startsWith(""));        System.out.println(trie.wordsWithPrefix("car", 10) + " " + trie.wordsWithPrefix("do", 10) + " " + trie.wordsWithPrefix("x", 10));        System.out.println(trie.wordsWithPrefix("", 3));        try {            trie.insert("Cat");        } catch (IllegalArgumentException e) {            System.out.println("error: " + e.getMessage());        }    }}

Code

nodes including the root: 10true false false true falsetrue false true true[car, card, care] [do, dog] [][car, card, care]error: only lowercase a-z is supported: C

Walk through the output.

Node count. cat creates 3 nodes (c, a, t). car reuses c, a and adds r. card adds d. care adds e. dog adds 3 nodes, and do reuses the first two. That is 3 + 1 + 1 + 1 + 3 = 9 nodes plus the root, so 10.
contains. "ca" is a path in the trie but not a stored word, so false. "cards" falls off the trie. The empty string is false, because we never inserted it (the root's flag is unset).
startsWith. "cab" is not a prefix of anything. The empty prefix is true, as every word starts with the empty string.
Autocomplete returns words in alphabetical order, and the limit stops the search early (the last line asks for the first 3 words overall).

Dry run of the insertions car, then card, then cat, tracking only what changes:

Operation	Path followed	New nodes created	`isWord` set on
insert `car`	root, `c`, `a`, `r`	`c`, `a`, `r` (3)	node `r`
insert `card`	root, `c`, `a`, `r`, `d`	`d` (1)	node `d`
insert `cat`	root, `c`, `a`, `t`	`t` (1)	node `t`

The prefix c-a is stored once, and is shared by all three words.

A map-based node for any alphabet

If the characters are not just lowercase letters, store children in a HashMap<Character, Node>. The logic is identical; only the child lookup changes. Here is a small version that handles letters, digits and symbols.

Java

// File: Main.javaimport java.util.HashMap;import java.util.Map;public class Main {    static class MapTrie {        private static class Node {            final Map<Character, Node> children = new HashMap<>();            boolean isWord;        }        private final Node root = new Node();        void insert(String word) {            Node node = root;            for (char c : word.toCharArray()) {                node = node.children.computeIfAbsent(c, k -> new Node());            }            node.isWord = true;        }        private Node find(String prefix) {            Node node = root;            for (char c : prefix.toCharArray()) {                node = node.children.get(c);                if (node == null) {                    return null;                }            }            return node;        }        boolean contains(String word) {            Node node = find(word);            return node != null && node.isWord;        }        boolean startsWith(String prefix) {            return find(prefix) != null;        }    }    public static void main(String[] args) {        MapTrie trie = new MapTrie();        trie.insert("c++");        trie.insert("c#");        trie.insert("c");        trie.insert("Java8");        System.out.println(trie.contains("c#") + " " + trie.contains("c+") + " " + trie.startsWith("c+") + " " + trie.contains("c"));        System.out.println(trie.contains("java8") + " " + trie.contains("Java8") + " " + trie.startsWith("Ja"));    }}

Code

true false true truefalse true true

This version is case-sensitive, because 'J' and 'j' are different keys, and works with '+' and '#', which the array version would reject. computeIfAbsent creates the child only if it is missing, which replaces the if (children[i] == null) block.

Trie, HashSet or sorted set?

Do not reach for a trie out of habit. Compare:

Need	`HashSet<String>`	Sorted set (`TreeSet<String>`)	Trie
Is this exact word present?	O(L) on average	O(L log n), as each comparison reads up to L characters	O(L)
Does any word start with this prefix?	O(n), scan everything	O(L log n) with `ceiling`	O(L)
List the words with a prefix, sorted	O(n)	O(L log n + k) with `subSet`	O(L + size of the subtrie)
Memory	Lower	Lower	Higher
Code size	Tiny	Tiny	A small class

A TreeSet can answer prefix queries too, using subSet(prefix, true, prefix + Character.MAX_VALUE, true), which gives the words from prefix up to the largest possible continuation of it. For many applications that is simpler and uses less memory, so a trie is not the only answer. Tries win when you need many prefix operations, per-prefix counts or the ability to walk the structure character by character (for example, to prune a search).

The program below checks the two approaches against each other: for every prefix of every word in a small dictionary, the trie and the TreeSet must return the same list.

Java

// File: Main.javaimport java.util.ArrayList;import java.util.List;import java.util.TreeSet;public class Main {    static class Trie {        private static class Node {            final Node[] children = new Node[26];            boolean isWord;        }        private final Node root = new Node();        void insert(String word) {            Node node = root;            for (char c : word.toCharArray()) {                if (node.children[c - 'a'] == null) {                    node.children[c - 'a'] = new Node();                }                node = node.children[c - 'a'];            }            node.isWord = true;        }        List<String> wordsWithPrefix(String prefix) {            Node node = root;            for (char c : prefix.toCharArray()) {                node = node.children[c - 'a'];                if (node == null) {                    return new ArrayList<>();                }            }            List<String> result = new ArrayList<>();            collect(node, new StringBuilder(prefix), result);            return result;        }        private void collect(Node node, StringBuilder path, List<String> result) {            if (node.isWord) {                result.add(path.toString());            }            for (int i = 0; i < 26; i++) {                if (node.children[i] != null) {                    path.append((char) ('a' + i));                    collect(node.children[i], path, result);                    path.deleteCharAt(path.length() - 1);                }            }        }    }    static List<String> viaTreeSet(TreeSet<String> words, String prefix) {        return new ArrayList<>(words.subSet(prefix, true, prefix + Character.MAX_VALUE, true));    }    public static void main(String[] args) {        String[] dictionary = {"tree", "trie", "try", "trip", "tripod", "tea", "ten", "to", "toe", "i", "in", "inn", "tree"};        Trie trie = new Trie();        TreeSet<String> sorted = new TreeSet<>();        for (String word : dictionary) {            trie.insert(word);            sorted.add(word);        }        int checked = 0;        boolean same = true;        for (String word : dictionary) {            for (int end = 0; end <= word.length(); end++) {                String prefix = word.substring(0, end);                same &= trie.wordsWithPrefix(prefix).equals(viaTreeSet(sorted, prefix));                checked++;            }        }        same &= trie.wordsWithPrefix("z").equals(viaTreeSet(sorted, "z"));        System.out.println("checked " + checked + " prefixes, identical results: " + same);        System.out.println(trie.wordsWithPrefix("tr"));    }}

Code

checked 55 prefixes, identical results: true[tree, trie, trip, tripod, try]

The duplicate "tree" in the dictionary does no harm to either structure: inserting a word twice just sets the same flag again (and a TreeSet ignores duplicates).

Complexity summary

Operation	Time	Notes
`insert(word)`	O(L)	`L` is the word length
`contains(word)`	O(L)	Independent of the number of words
`startsWith(prefix)`	O(L)
Autocomplete (`k` results)	O(L + nodes visited)	At least `k`, at most the size of the subtrie
Space	O(total characters × alphabet) worst case	About `26` references per node with arrays

Edge cases and common mistakes

Treating "node exists" as "word exists". contains must check isWord. startsWith must not.
Forgetting to set isWord at the end of an insert.
Words that are prefixes of other words (car and card). The flag handles it. Check that you do not mark a node as a word only when it is a leaf.
The empty string. Decide whether it is a valid word. Our trie treats it as not inserted, and startsWith("") is true.
Characters outside a to z. An array node throws or crashes. Validate, or use a map.
Case. "Cat" and "cat" are different words unless you normalise. Use toLowerCase(Locale.ROOT) if the problem is case-insensitive.
Memory. A trie of many long, unrelated words can use far more memory than a HashSet. Mention it.
Returning results in an unexpected order. Array children give alphabetical order. A HashMap does not.
Unicode. Characters beyond a simple alphabet, and characters made of several code units, need extra care (see the Unicode note in the strings article).
Deleting words. Removing the isWord flag is easy. Freeing nodes that are no longer needed requires walking back up. Many problems let you skip real deletion.

Exercises

Exercise 1

Trace

Insert the words to, tea, ten, i, in into an empty trie. Draw the trie, mark the word endings, and state how many nodes there are (not counting the root). Then answer: is te a stored word? Does any word start with te? What does autocomplete for te return?

Exercise 2: Count words with a prefix

Extend the trie so that countWithPrefix(prefix) returns how many stored words begin with the prefix, in O(L) time. A word equal to the prefix counts.

Exercise 3: Wildcard search

Design a structure with addWord(word) and search(pattern), where the pattern may contain the character '.', which matches any one letter. For example, after adding bad, dad and mad, search("b..") is true, search(".ad") is true, and search("b.") is false.

Exercise 4: Debug

This trie has two bugs. After inserting apple, search("app") wrongly returns true. And once you fix that, search("apple") surprisingly returns false. Find and fix both.

Java

void insert(String word) {    Node node = root;    for (char c : word.toCharArray()) {        if (node.children[c - 'a'] == null) {            node.children[c - 'a'] = new Node();        }        node = node.children[c - 'a'];    }}boolean search(String word) {    Node node = root;    for (char c : word.toCharArray()) {        node = node.children[c - 'a'];        if (node == null) {            return false;        }    }    return true;}

Exercise 5: Interview-style, replace words

A dictionary holds roots such as cat, bat and rat. In a sentence, replace every word that starts with a root by the shortest root that is a prefix of it. For the roots ["cat", "bat", "rat"] and the sentence "the cattle was rattled by the battery" the answer is "the cat was rat by the bat". Words with no matching root stay as they are.

Show solutionHide solution

The trie after the five insertions (a * marks a word end):

Code

(root) ├── t │    ├── o*          "to" │    └── e │         ├── a*     "tea" │         └── n*     "ten" └── i*               "i"      └── n*          "in"

Counting nodes (without the root): t, o, e, a, n under t, which is 5 nodes, and i, n under i, which is 2 more. The total is 7.

Is te a stored word? No. The node exists, but its isWord flag is not set.
Does any word start with te? Yes: tea and ten.
Autocomplete for te returns tea, ten, in alphabetical order.

Java

// File: Main.javaimport java.util.ArrayList;import java.util.List;public class Main {    static class Node {        final Node[] children = new Node[26];        boolean isWord;    }    static int nodes = 0;    static void insert(Node root, String word) {        Node node = root;        for (char c : word.toCharArray()) {            if (node.children[c - 'a'] == null) {                node.children[c - 'a'] = new Node();                nodes++;            }            node = node.children[c - 'a'];        }        node.isWord = true;    }    static void collect(Node node, StringBuilder path, List<String> out) {        if (node.isWord) {            out.add(path.toString());        }        for (int i = 0; i < 26; i++) {            if (node.children[i] != null) {                path.append((char) ('a' + i));                collect(node.children[i], path, out);                path.deleteCharAt(path.length() - 1);            }        }    }    public static void main(String[] args) {        Node root = new Node();        for (String w : new String[] {"to", "tea", "ten", "i", "in"}) {            insert(root, w);        }        Node te = root.children['t' - 'a'].children['e' - 'a'];        List<String> suggestions = new ArrayList<>();        collect(te, new StringBuilder("te"), suggestions);        System.out.println("nodes: " + nodes + ", te is a word: " + te.isWord + ", suggestions: " + suggestions);    }}

Code

nodes: 7, te is a word: false, suggestions: [tea, ten]

Exercise 2

Show solutionHide solution

Add a counter to each node, wordsBelow, that records how many stored words pass through (or end at) that node. When inserting a word, increment the counter of every node on the path, including the node where it ends. Then countWithPrefix walks the prefix and returns the counter of the node reached, or 0 if the path does not exist.

To avoid counting the same word twice, only increment the counters if the word was not already stored. Check that with contains before inserting. Time O(L) per operation.

Java

// File: Main.javapublic class Main {    static class CountingTrie {        private static class Node {            final Node[] children = new Node[26];            boolean isWord;            int wordsBelow;                 // number of stored words passing through or ending at this node        }        private final Node root = new Node();        private Node find(String s) {            Node node = root;            for (char c : s.toCharArray()) {                node = node.children[c - 'a'];                if (node == null) {                    return null;                }            }            return node;        }        boolean contains(String word) {            Node node = find(word);            return node != null && node.isWord;        }        void insert(String word) {            if (contains(word)) {                return;                      // do not count a duplicate twice            }            Node node = root;            node.wordsBelow++;            for (char c : word.toCharArray()) {                if (node.children[c - 'a'] == null) {                    node.children[c - 'a'] = new Node();                }                node = node.children[c - 'a'];                node.wordsBelow++;            }            node.isWord = true;        }        int countWithPrefix(String prefix) {            Node node = find(prefix);            return node == null ? 0 : node.wordsBelow;        }    }    public static void main(String[] args) {        CountingTrie trie = new CountingTrie();        for (String w : new String[] {"apple", "app", "apply", "ape", "bat", "app"}) {            trie.insert(w);        }        System.out.println(trie.countWithPrefix("ap") + " " + trie.countWithPrefix("app") + " " + trie.countWithPrefix("appl")                + " " + trie.countWithPrefix("b") + " " + trie.countWithPrefix("z") + " " + trie.countWithPrefix(""));    }}

Code

4 3 2 1 0 5

There are five distinct words (app was inserted twice). Four start with ap (apple, app, apply, ape), three start with app, two with appl, one with b, none with z, and the empty prefix matches all five.

Exercise 3

Show solutionHide solution

Store the words in an ordinary trie. To search a pattern, use a recursive walk that takes the current node and the position in the pattern.

If the pattern character is a letter, follow that one child (if it exists).
If it is '.', try every existing child, and return true if any of them leads to a match.
At the end of the pattern, the answer is the node's isWord.

In the worst case a pattern of all dots explores the whole trie below, so a query can cost up to O(total nodes), but a query with k dots costs at most about 26^k branches, and in practice the trie prunes most of them.

Java

// File: Main.javapublic class Main {    static class WordDictionary {        private static class Node {            final Node[] children = new Node[26];            boolean isWord;        }        private final Node root = new Node();        void addWord(String word) {            Node node = root;            for (char c : word.toCharArray()) {                if (node.children[c - 'a'] == null) {                    node.children[c - 'a'] = new Node();                }                node = node.children[c - 'a'];            }            node.isWord = true;        }        boolean search(String pattern) {            return search(root, pattern, 0);        }        private boolean search(Node node, String pattern, int position) {            if (position == pattern.length()) {                return node.isWord;            }            char c = pattern.charAt(position);            if (c == '.') {                for (Node child : node.children) {            // try every possible letter                    if (child != null && search(child, pattern, position + 1)) {                        return true;                    }                }                return false;            }            Node child = node.children[c - 'a'];            return child != null && search(child, pattern, position + 1);        }    }    public static void main(String[] args) {        WordDictionary dictionary = new WordDictionary();        dictionary.addWord("bad");        dictionary.addWord("dad");        dictionary.addWord("mad");        System.out.println(dictionary.search("pad") + " " + dictionary.search("bad") + " " + dictionary.search(".ad") + " " + dictionary.search("b.."));        System.out.println(dictionary.search("b.") + " " + dictionary.search("...") + " " + dictionary.search("....") + " " + dictionary.search(""));    }}

Code

false true true truefalse true false false

"b." is false because every stored word has three letters, and "..." matches any of them. The empty pattern is false, since no empty word was added.

Exercise 4

Show solutionHide solution

Two bugs:

insert never sets isWord. After walking the path, nothing marks the end of the word. So no word is ever recorded as a word.
search never checks isWord. It returns true as soon as it can follow all the characters. That makes it behave like startsWith.

With both bugs present, search returns true for every path that exists, so search("app") and search("apple") are both true (the first is wrong). If you fix only search, then search("app") correctly becomes false, but search("apple") also becomes false, because the end flag was never set. That second symptom is what shows that insert is broken too. Both fixes are needed.

Java

// File: Main.javapublic class Main {    static class Node {        final Node[] children = new Node[26];        boolean isWord;    }    static void insertBuggy(Node root, String word) {        Node node = root;        for (char c : word.toCharArray()) {            if (node.children[c - 'a'] == null) {                node.children[c - 'a'] = new Node();            }            node = node.children[c - 'a'];        }    }    static void insertFixed(Node root, String word) {        Node node = root;        for (char c : word.toCharArray()) {            if (node.children[c - 'a'] == null) {                node.children[c - 'a'] = new Node();            }            node = node.children[c - 'a'];        }        node.isWord = true;                       // fix 1: mark the end of the word    }    static boolean searchBuggy(Node root, String word) {        Node node = root;        for (char c : word.toCharArray()) {            node = node.children[c - 'a'];            if (node == null) {                return false;            }        }        return true;    }    static boolean searchFixed(Node root, String word) {        Node node = root;        for (char c : word.toCharArray()) {            node = node.children[c - 'a'];            if (node == null) {                return false;            }        }        return node.isWord;                       // fix 2: the path must end a stored word    }    public static void main(String[] args) {        Node buggy = new Node();        insertBuggy(buggy, "apple");        System.out.println("buggy: app=" + searchBuggy(buggy, "app") + " apple=" + searchBuggy(buggy, "apple"));        Node fixed = new Node();        insertFixed(fixed, "apple");        System.out.println("search fixed only: app=" + searchFixed(buggy, "app") + " apple=" + searchFixed(buggy, "apple"));        System.out.println("both fixed: app=" + searchFixed(fixed, "app") + " apple=" + searchFixed(fixed, "apple"));    }}

Code

buggy: app=true apple=truesearch fixed only: app=false apple=falseboth fixed: app=false apple=true

Exercise 5

Show solutionHide solution

Put all roots into a trie. For each word of the sentence, walk down the trie character by character. The first time you reach a node that ends a root, that root is the shortest matching prefix, so output it and stop. If the walk falls off the trie (a missing child) before reaching any root end, keep the word unchanged.

Because we stop at the first root end, we automatically get the shortest root when several roots are prefixes of the word (for example c and cat). Time is O(total characters) for the sentence plus building the trie.

Java

// File: Main.javapublic class Main {    static class Node {        final Node[] children = new Node[26];        boolean isRoot;    }    static void addRoot(Node root, String word) {        Node node = root;        for (char c : word.toCharArray()) {            if (node.children[c - 'a'] == null) {                node.children[c - 'a'] = new Node();            }            node = node.children[c - 'a'];        }        node.isRoot = true;    }    // The shortest root that is a prefix of word, or the word itself if there is none.    static String replace(Node root, String word) {        Node node = root;        for (int i = 0; i < word.length(); i++) {            node = node.children[word.charAt(i) - 'a'];            if (node == null) {                return word;                       // fell off the trie: no root matches            }            if (node.isRoot) {                return word.substring(0, i + 1);   // the first root end is the shortest root            }        }        return word;    }    static String replaceWords(String[] roots, String sentence) {        Node trieRoot = new Node();        for (String r : roots) {            addRoot(trieRoot, r);        }        StringBuilder out = new StringBuilder();        for (String word : sentence.split(" ")) {            if (out.length() > 0) {                out.append(' ');            }            out.append(replace(trieRoot, word));        }        return out.toString();    }    public static void main(String[] args) {        System.out.println(replaceWords(new String[] {"cat", "bat", "rat"}, "the cattle was rattled by the battery"));        System.out.println(replaceWords(new String[] {"a", "b", "c"}, "aadsfasf absbs bbab cadsfafs"));        System.out.println(replaceWords(new String[] {"c", "cat"}, "category cart dog"));        System.out.println("[" + replaceWords(new String[] {"x"}, "") + "]");    }}

Code

the cat was rat by the bata a b cc c dog[]

In the third example, both c and cat are roots, and category starts with both. The walk reaches the end of root c first, so the shortest root c wins. dog has no root, so it is unchanged.

Where to go next

Next: Range Queries and Disjoint Set Union finishes the advanced module with two more specialised structures.
Related: a trie is a good tool for pruning in Recursion and Backtracking, for example in word-search problems where you can stop as soon as a path is no longer a prefix of any word.
Practice habit: for every prefix problem, ask first whether a HashSet or a sorted structure is enough. If it is, use it. Reach for a trie when you need many prefix queries, counts per prefix, or to prune a search.

Connected lessons

References

Show all 5 →

Linked from 5 guides

Other pages in the library that point here.

Show all 5 →

Tries and Prefix-Based Search

For

Level

Before you start

Key takeaways

What you will learn

The idea

How the algorithms work

Node representation

A trie in Java

A map-based node for any alphabet

Trie, HashSet or sorted set?

Complexity summary

Edge cases and common mistakes

Exercises

Trace

Exercise 2: Count words with a prefix

Exercise 3: Wildcard search

Exercise 4: Debug

Exercise 5: Interview-style, replace words

Where to go next

Connected lessons

Linked from 5 guides

Keep reading

How to Learn Data Structures and Algorithms Without Burning Out

The OA Landscape: Platforms, Formats, Proctoring and Rules

A LinkedIn Profile That Gets Recruiter Messages