Skip to main content
PreparationZone Logo
PreparationZone
Sign up
Back to Coding

Coding · Medium · Free

Longest word in dictionary that can be built one character at a time

CodingTrieFresher
Model answer

Approach

  • Insert all words into trie; mark ends.
  • DFS from root preferring deeper valid words.
  • A word is valid only if every prefix is also marked as a complete word.

Java Solution

Java
public class LongestWordTrie {
    String best = "";
    void dfs(TrieNode node, StringBuilder path) {
        if (path.length() > best.length() || (path.length() == best.length() && path.toString().compareTo(best) < 0))
            best = path.toString();
        for (var e : node.children.entrySet()) {
            if (!e.getValue().isEnd) continue;
            path.append(e.getKey());
            dfs(e.getValue(), path);
            path.deleteCharAt(path.length() - 1);
        }
    }
}
Complexity
TimeO(total chars)
SpaceO(total chars)
Interview tip: Interview checks you understand prefix validity, not just storing strings.