Longest Word in Dictionary

Given an array of strings words, return the longest word that can be built one character at a time by other words in the array. If multiple answers, return the lexicographically smallest.

Example 1

Input: ["w","wo","wor","word","work"] → Output: "word"

Example 2

Input: ["a","banana","app","appl","ap","apply","apple"] → Output: "apple"

Solution Approach

Build a Trie. For each word, it is valid if every prefix is also in the Trie as a complete word. BFS/DFS from root finding longest valid path.

Insert all words into Trie.
BFS from root: add a node to queue only if it represents a complete word (isEnd=true).
Track the longest (then lexicographically smallest) word.

Java

import java.util.*;

class Solution {
    public String longestWord(String[] words) {
        Trie trie = new Trie();
        for (String w : words) trie.insert(w);
        String result = "";
        // BFS
        Queue<String> q = new LinkedList<>();
        q.offer("");
        while (!q.isEmpty()) {
            String cur = q.poll();
            if (cur.length() > result.length() || (cur.length() == result.length() && cur.compareTo(result) < 0))
                result = cur;
            for (char c = 'a'; c <= 'z'; c++) {
                String next = cur + c;
                if (trie.search(next)) q.offer(next);
            }
        }
        return result;
    }
    // Simple Trie for this problem
    static class Trie {
        boolean[][] isEnd; // simplified
        Map<String,Boolean> set = new HashSet<>() {{ }};
        Set<String> words = new java.util.HashSet<>();
        public void insert(String w) { words.add(w); }
        public boolean search(String w) { return words.contains(w); }
    }
}

Time Complexity: O(N * L) where L=max word length
Space Complexity: O(N * L)