Longest Word in Dictionary

MediumTrie · Hash Set · Sorting🧩 Trie LeetCode #720 ↗Updated Oct 30, 2026

Problem

You are given an array words of lowercase strings. A word is buildable if you can grow it one letter at a time from the right, and every intermediate prefix (lengths 1, 2, …) is also in words. Return the longest buildable word; break ties by the lexicographically smallest one, and return "" if no word qualifies.

Inputwords = ["w","wo","wor","worl","world"]Output"world"

Inputwords = ["a","banana","app","appl","ap","apply","apple"]Output"apple" ("apply" ties on length but is larger)

Inputwords = ["xy","yz"]Output"" (no single letters)

1 ≤ words.length ≤ 1000 · 1 ≤ words[i].length ≤ 30 · lowercase English letters only

Try it yourself

Java

class Solution {
    public String longestWord(String[] words) {
        
    }
}

Your code is saved in this browser.Submit on LeetCode ↗

Key insight

Put the words in a trie and mark word ends. A word is buildable exactly when every node on its path is a word end, so a DFS that only steps into marked children visits precisely the buildable words.

PatternTrie

Instinct Many words, shared prefixes, and questions like "starts with", autocomplete, wildcard match or "search a board for all these words" - build a prefix tree.

Memory hack Words share their beginnings, so store each beginning once - walk one letter per step, and an end flag marks where a real word stops.

Open the Trie guide →

Approaches

Brute ForceCheck Every Prefix by Scanning the List

Time O(n² · L²)Space O(1)

For each word, test each of its proper prefixes by scanning the whole array for an equal string. Keep the best candidate by (length desc, text asc). Direct translation of the definition, nothing clever.

Java

public String longestWord(String[] words) {
    String best = "";
    for (String w : words) {
        boolean ok = true;
        for (int len = 1; len < w.length() && ok; len++) {
            ok = contains(words, w.substring(0, len));
        }
        if (ok && (w.length() > best.length()
                || (w.length() == best.length() && w.compareTo(best) < 0))) {
            best = w;
        }
    }
    return best;
}

private boolean contains(String[] words, String target) {
    for (String s : words) {
        if (s.equals(target)) return true;
    }
    return false;
}

Correct but quadratic in the number of words — too slow beyond toy input.

BetterSort, then Grow a Set of Buildable Words

Time O(n log n · L)Space O(n · L)

Sort the words; then every prefix is processed before the word that extends it. A word is buildable iff it has length 1 or its prefix minus the last letter is already in the built set. Because shorter words come first, one pass decides everything.

Java

public String longestWord(String[] words) {
    String[] sorted = words.clone();
    Arrays.sort(sorted);
    Set<String> built = new HashSet<>();
    String best = "";
    for (String w : sorted) {
        if (w.length() == 1 || built.contains(w.substring(0, w.length() - 1))) {
            built.add(w);
            // sorted order means an equal-length later word is never smaller
            if (w.length() > best.length()) best = w;
        }
    }
    return best;
}

Simple and fast; the sort dominates and string hashing costs O(L) per lookup.

OptimalTrie + DFS Through Word-End Nodes

Time O(n · L)Space O(n · L)

Insert all words into a 26-ary trie, storing the full word at its end node. DFS from the root but only descend into children that end a word: every reached node is buildable. Visiting children in a..z order and replacing the answer only on strictly longer words gives the smallest tie automatically.

Java

private static class Node {
    Node[] next = new Node[26];
    String word; // non-null when a word ends here
}

private String best = "";

public String longestWord(String[] words) {
    Node root = new Node();
    for (String w : words) {
        Node cur = root;
        for (char c : w.toCharArray()) {
            if (cur.next[c - 'a'] == null) cur.next[c - 'a'] = new Node();
            cur = cur.next[c - 'a'];
        }
        cur.word = w;
    }
    best = "";
    dfs(root);
    return best;
}

private void dfs(Node node) {
    for (Node child : node.next) {
        if (child != null && child.word != null) {
            if (child.word.length() > best.length()) best = child.word;
            dfs(child); // only buildable words are ever reached
        }
    }
}

Linear in total characters, no sorting, and no substring allocation.

Pro tip

Recursion depth is at most the word length (30), so DFS is safe; a BFS by levels works just as well.

At a glance

Level	Approach	Time	Space
Brute Force	Check Every Prefix by Scanning the List	`O(n² · L²)`	`O(1)`
Better	Sort, then Grow a Set of Buildable Words	`O(n log n · L)`	`O(n · L)`
Optimal	Trie + DFS Through Word-End Nodes	`O(n · L)`	`O(n · L)`

Common pitfalls

Forgetting that every prefix must exist — checking only the len-1 prefix without sorting.
Wrong tie-break: return the smallest word among the longest, not the first one seen.
In the trie DFS, stepping into a child that is not a word end breaks the chain.

Interview tips

Restate “buildable” as “all prefixes present” before coding.
Mention the sort+set idea first; it's short and convincing, then offer the trie.
Explain why a–z DFS order plus a strict > handles ties for free.

Pattern

Trie with end markers → questions about words whose every prefix must also be a word.

My notes saved in this browser