Trie Prefix Matching

Description

Some questions care about every prefix of a word, not just the word: "the longest word that can be built one letter at a time from other words in the list", or "replace each word in a sentence with the shortest dictionary root it starts with". A trie holds all the prefixes on one path, so each question becomes a single walk.

This skill covers three versions of that walk: requiring an end mark on every node, stopping at the first end mark, and keeping the last one. It also covers the tie-break and "no answer" rules that make the results well defined.

We'll go from simple to more technical:

1. The pattern: the longest word whose every prefix is also a word.
2. A second flavor: Replace Words, stopping at the first end mark.
3. Where prefix walks show up (stemming, URL routing, IP longest-prefix match).
4. What breaks it: checking only the full word, shortest versus longest, ties, no answer.

The approach

boolean allPrefixesAreWords(String word) {
    TrieNode node = root;
    for (char c : word.toCharArray()) {
        node = node.next[c - 'a'];
        if (node == null || !node.isEnd) return false;   // this prefix isn't itself a stored word
    }
    return true;
}

String longestWordWithAllPrefixes(String[] words) {
    for (String w : words) insert(w);
    String best = "";
    for (String w : words) {
        if (allPrefixesAreWords(w) && (w.length() > best.length()
                || (w.length() == best.length() && w.compareTo(best) < 0))) {
            best = w;                                    // longer, or same length and smaller
        }
    }
    return best;
}

def all_prefixes_are_words(word: str) -> bool:
    node = root
    for c in word:
        node = node.next.get(c)
        if node is None or not node.is_end:
            return False                                 # this prefix isn't itself a stored word
    return True


def longest_word_with_all_prefixes(words: list[str]) -> str:
    for w in words:
        insert(w)
    best = ""
    for w in words:
        if all_prefixes_are_words(w) and (len(w) > len(best) or (len(w) == len(best) and w < best)):
            best = w                                     # longer, or same length and smaller
    return best

"bread" qualifies only if "b", "br", "bre", "brea" and "bread" are all in the list - every node on its path must carry an end mark, not just the last. A plain search(w) checks only the last one. The tie-break (lexicographically smallest among equally long words) makes the answer unique, and "" is the answer when no word qualifies, for instance when there are no one-letter words.

A second flavor: stop at the first end mark

Replace each word by the shortest root that is a prefix of it ("cattle" with root "cat" becomes "cat"):

String shortestRoot(String word) {
    TrieNode node = root;
    for (int i = 0; i < word.length(); i++) {
        node = node.next[word.charAt(i) - 'a'];
        if (node == null) return word;                 // no root is a prefix
        if (node.isEnd) return word.substring(0, i + 1);   // the first end mark is the shortest root
    }
    return word;
}

def shortest_root(word: str) -> str:
    node = root
    for i, c in enumerate(word):
        node = node.next.get(c)
        if node is None:
            return word                                  # no root is a prefix
        if node.is_end:
            return word[:i + 1]                          # the first end mark is the shortest root
    return word

Walking down the word's own path meets the roots in order of length, so the first end mark is the shortest. Continuing to the last end mark returns the longest root instead ("cat" and "catt" for "cattle" would give "catt").

Where you'll see it

Stemming and lemmatization shorten words to dictionary roots; URL routers match the most (or least) specific registered path prefix; IP forwarding picks the longest matching network prefix - the same walk, keeping the last end mark seen. Checking that every intermediate step is itself valid (every prefix a word) is how incremental builds validate each step of a chain.

Which tool for which job?

Common mistakes

Check yourself

Try to answer before opening each one - recalling beats re-reading.

1. Why isn't search(word) enough for "every prefix is also a word"?

2. How does a single walk find the shortest root of a word?

3. What does the longest-word question return when no word qualifies?

Key takeaways

• A word's prefixes all lie on its path; one walk checks them.
• "Every prefix is a word": every node on the path needs an end mark.
• Shortest root: stop at the first end mark; longest: keep the last.
• Make tie-breaks and "no answer" explicit.