Longest Word in Dictionary

How to solve Longest Word in Dictionary: the approach in brief

The problem

Given an array of strings words representing an English Dictionary, return the longest word in words that can be built one character at a time by other words in words.

Pattern

Longest Word in Dictionary is a Design Patterns problem, in the Tries subpattern. The pattern covers tries, LRU/LFU cache, and data structure design

Implement Trie data structure for prefix-based operations and autocomplete systems.

Approach outline

1. Consider using a data structure that efficiently supports prefix searching and word construction, such as a Trie.
2. Build a Trie from the list of words, where each node represents a character, to help check if prefixes exist.
3. While traversing the Trie, keep track of nodes that mark the end of valid words to ensure each prefix is valid.

Complexity

The reference solution runs in O(n) time and O(t) space.

Asked at

Longest Word in Dictionary has been reported in interviews at Goldman Sachs, Facebook.