Longest Word in Dictionary solution and explanation
Google
9 more videos on this problem
Longest Word in Dictionary (LeetCode 720. Algorithm Explained)Nick White · 8:04 · 19K views
Longest Word in Dictionary | Leetcode 720Pepcoding · 24:16 · 5K views
花花酱 LeetCode 720. Longest Word in Dictionary - 刷题找工作 EP109Hua Hua · 20:08 · 4K views
Leetcode 720 - Trie | Longest Word Dictionary | Advanced AlgorithmNideesh Terapalli · 11:34 · 3K views
Leetcode 720 Longest Word in DictionaryRen Zhang · 14:35 · 2K views
Leetcode 720. Longest Word in Dictionary (Trie)LetsCode · 11:57 · 400 views
91. Leetcode 720 Longest Word in Dictionary爱学习的饲养员 · 12:32 · 185 views
Leetcode 720. Longest Word in DictionaryAlgorithms for Big Bucks · 9:51 · 104 views
Longest Word in Dictionary | LeetCode #720 | Python Solution Explained Step-by-StepNidhi Chouhan · 22:36 · 38 views
No Sound Leetcode 720: Longest Word in DictionaryExtremeProgrammer · 2:13 · 23 views
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.
If there is more than one possible answer, return the longest word with the smallest lexicographical order. If there is no answer, return the empty string.
Note that the word should be built from left to right with each additional character being added to the end of a previous word.
Example 1:
Input: words = ["w","wo","wor","worl","world"] Output: "world" Explanation: The word "world" can be built one character at a time by "w", "wo", "wor", and "worl".
Example 2:
Input: words = ["a","banana","app","appl","ap","apply","apple"] Output: "apple" Explanation: Both "apply" and "apple" can be built from other words in the dictionary. However, "apple" is lexicographically smaller than "apply".
Constraints:
1 <= words.length <= 10001 <= words[i].length <= 30words[i]consists of lowercase English letters.
Approach overview
Problem Overview: You are given a list of words. The task is to find the longest word that can be built one character at a time by other words in the same list. Every prefix of the word must also exist in the dictionary. If multiple answers exist, return the lexicographically smallest one.
Approach 1: Sorting and Set-based Verification (O(n log n) time, O(n) space)
This approach sorts the word list lexicographically so smaller words appear before their extensions. Iterate through the sorted list and maintain a HashSet of valid buildable words. A word is valid if its prefix word[:-1] already exists in the set. If valid, insert it into the set and update the current best answer when its length is greater than the previous result. Sorting ensures that shorter prefixes are processed before longer candidates. This method relies heavily on fast membership checks using a hash table and works well for most interview constraints.
Approach 2: Trie-based Approach (O(n * L) time, O(n * L) space)
A Trie stores all words while preserving prefix relationships. Insert every word into the Trie and mark nodes that represent completed words. Then perform DFS or iterate through the words to verify that every prefix node along the path is marked as a valid word. Only paths where each intermediate node represents a completed word are considered buildable. Track the longest word encountered, resolving ties using lexicographic order. This approach leverages the natural prefix structure of a Trie and avoids repeated substring checks common with plain string operations.
The Trie solution scales well when the dataset contains many shared prefixes because each character is processed once during insertion and traversal. However, it requires more memory due to storing nodes for each character.
Recommended for interviews: The sorting + hash set approach is typically expected in interviews. It is concise, easy to reason about, and demonstrates efficient use of sorting and hash lookups. The Trie solution shows deeper knowledge of prefix data structures and is a strong alternative when discussing optimizations or follow‑up questions.
Approach 1: Sorting and Set-based Verification
This approach involves sorting the words array. By sorting, words that could potentially be built upon would appear earlier in the list. After sorting, we use a set to keep track of words that can be built character by character.
The process is as follows:
- Sort the words array first based on length, then lexicographically.
- Initialize a set with an empty string.
- Iterate through each word in the sorted array:
- Check if the prefix of the word (without the last character) exists in the set.
- If it exists, add the whole word to the set.
- Track the longest word found during the iteration.
This is efficient due to the pre-sorting which allows easy checking and ensures we are building words correctly by the constraints given.
def longestWord(words):
words.sort(key=lambda x: (len(x), x))
built, res = {""}, ""
for word in words:
if word[:-1] in built:
built.add(word)
if len(word) > len(res):
res = word
return res
words = ["w", "wo", "wor", "worl", "world"]
print(longestWord(words))import java.util.HashSet;
import java.util.Arrays;
public class Solution {
public static String longestWord(String[] words) {
Arrays.sort(words, (a, b) -> (a.length() == b.length() ? a.compareTo(b) : Integer.compare(a.length(), b.length())));
HashSet<String> built = new HashSet<>();
built.add("");
String res = "";
for (String word : words) {
if (built.contains(word.substring(0, word.length() - 1))) {
built.add(word);
if (word.length() > res.length()) res = word;
}
}
return res;
}
public static void main(String[] args) {
String[] words = {"w", "wo", "wor", "worl", "world"};
System.out.println(longestWord(words));
}
}#include <iostream>
#include <vector>
#include <string>
#include <unordered_set>
#include <algorithm>
using namespace std;
string longestWord(vector<string>& words) {
sort(words.begin(), words.end(), [](const string &a, const string &b) {
return a.size() == b.size() ? a < b : a.size() < b.size();
});
unordered_set<string> built;
built.insert("");
string res;
for (string &word : words) {
if (built.find(word.substr(0, word.size() - 1)) != built.end()) {
built.insert(word);
if (word.size() > res.size()) res = word;
}
}
return res;
}
int main() {
vector<string> words = {"w", "wo", "wor", "worl", "world"};
cout << longestWord(words) << endl;
return 0;
}function longestWord(words) {
words.sort((a, b) => a.length === b.length ? (a < b ? -1 : 1) : a.length - b.length);
let built = new Set([""]);
let res = "";
for (let word of words) {
if (built.has(word.slice(0, -1))) {
built.add(word);
if (word.length > res.length) res = word;
}
}
return res;
}
const words = ["w", "wo", "wor", "worl", "world"];
console.log(longestWord(words));#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
int compare(const void *a, const void *b) {
const char *word1 = *(const char **)a;
const char *word2 = *(const char **)b;
if (strlen(word1) == strlen(word2)) {
return strcmp(word1, word2);
}
return strlen(word1) - strlen(word2);
}
bool canBeBuilt(char *word, char **set, int setLen) {
char prefix[strlen(word)];
strncpy(prefix, word, strlen(word) - 1);
prefix[strlen(word) - 1] = '\0';
for (int i = 0; i < setLen; i++) {
if (strcmp(set[i], prefix) == 0) {
return true;
}
}
return false;
}
char* longestWord(char** words, int wordsSize) {
qsort(words, wordsSize, sizeof(char *), compare);
char **set = (char **)malloc(wordsSize * sizeof(char *));
int setLen = 0;
set[setLen++] = "";
char *longestWord = "";
for (int i = 0; i < wordsSize; i++) {
if (canBeBuilt(words[i], set, setLen)) {
set[setLen++] = words[i];
if (strlen(words[i]) > strlen(longestWord)) {
longestWord = words[i];
}
}
}
free(set);
return longestWord;
}
int main() {
char *words[] = {"w", "wo", "wor", "worl", "world"};
printf("%s\n", longestWord(words, 5));
return 0;
}using System;
using System.Collections.Generic;
public class Solution {
public static string LongestWord(string[] words) {
Array.Sort(words, (a, b) => (a.Length == b.Length) ? string.Compare(a, b) : a.Length - b.Length);
HashSet<string> built = new HashSet<string> {""};
string res = "";
foreach (string word in words) {
if (built.Contains(word.Substring(0, word.Length - 1))) {
built.Add(word);
if (word.Length > res.Length) res = word;
}
}
return res;
}
public static void Main(string[] args) {
string[] words = {"w", "wo", "wor", "worl", "world"};
Console.WriteLine(LongestWord(words));
}
}Python's concise syntax and dynamic typing make this implementation straightforward. It utilizes a prefix check with a set and manages the longest word in a single iteration over the sorted words list. Python's built-in sorting handles the ordering based on length and lexicography.
Time complexity: O(N log N + N * M), where sorting and prefix lookups determine the time complexity.
Space complexity: O(N * M), owing to the storage in the set for valid words.
Approach 2: Trie-based Approach
This approach uses a Trie (prefix tree) to store the words. By utilizing this data structure, we aim to verify if a word can be constructed by progressively building on its prefixes.
The steps are:
- Build a Trie from the words array.
- For each word, check if all its prefixes are present in the Trie.
- Track the longest word that meets the criterion.
- If multiple words have the same length, select the lexicographically smallest one.
This combines efficient storage and lookup, with Prefix trees naturally lending themselves to this problem due to their structure.
class TrieNode:
def __init__(self):
self.children = {}
self.end_of_word = False
class Solution:
def longestWord(self, words):
root = TrieNode()
for word in sorted(words):
current_node = root
for char in word:
if char not in current_node.children:
current_node.children[char] = TrieNode()
current_node = current_node.children[char]
current_node.end_of_word = True
def canBuild(word):
current_node = root
for char in word:
current_node = current_node.children.get(char)
if not current_node.end_of_word:
return False
return True
longest = ""
for word in sorted(words, key=lambda x: (-len(x), x)):
if canBuild(word) and len(word) > len(longest):
longest = word
return longest
words = ["w", "wo", "wor", "worl", "world"]
solution = Solution()
print(solution.longestWord(words))#include <iostream>
#include <vector>
#include <unordered_map>
#include <algorithm>
using namespace std;
class TrieNode {
public:
unordered_map<char, TrieNode*> children;
bool end_of_word = false;
};
class Solution {
public:
string longestWord(vector<string>& words) {
TrieNode* root = new TrieNode();
for (string word : words) {
TrieNode* current = root;
for (char ch : word) {
if (!current->children.count(ch)) {
current->children[ch] = new TrieNode();
}
current = current->children[ch];
}
current->end_of_word = true;
}
string result;
for (string word : words) {
if (canBuild(root, word) && (word.size() > result.size() || (word.size() == result.size() && word < result))) {
result = word;
}
}
return result;
}
private:
bool canBuild(TrieNode* root, const string& word) {
TrieNode* current = root;
for (char ch : word) {
current = current->children[ch];
if (!current->end_of_word) {
return false;
}
}
return true;
}
};
int main() {
Solution solution;
vector<string> words = {"w", "wo", "wor", "worl", "world"};
cout << solution.longestWord(words) << endl;
return 0;
}This Python solution involves first inserting all words into a Trie structure and then checking each sorted word to verify that every prefix exists within the Trie. The check is aided by the use of an end_of_word flag to determine the presence of complete valid prefixes every step of the way.
Time complexity: O(N * M), where creating the Trie and checking word validity both operate over each character of every word.
Space complexity: O(N * M) for the Trie data structure.
Approach 3: Trie
We can use a trie to store all the words, then traverse all the words to determine if the current word can be formed by adding one letter at a time from other words in the trie. Find the longest word that meets the condition and has the smallest lexicographical order.
The time complexity is O(L), and the space complexity is O(L), where L is the sum of the lengths of all words.
class Trie {
children: (Trie | null)[] = new Array(26).fill(null);
isEnd: boolean = false;
insert(w: string): void {
let node: Trie = this;
for (let i = 0; i < w.length; i++) {
const idx: number = w.charCodeAt(i) - 'a'.charCodeAt(0);
if (node.children[idx] === null) {
node.children[idx] = new Trie();
}
node = node.children[idx]!;
}
node.isEnd = true;
}
search(w: string): boolean {
let node: Trie = this;
for (let i = 0; i < w.length; i++) {
const idx: number = w.charCodeAt(i) - 'a'.charCodeAt(0);
if (node.children[idx] === null || !node.children[idx]!.isEnd) {
return false;
}
node = node.children[idx]!;
}
return true;
}
}
function longestWord(words: string[]): string {
const trie = new Trie();
for (const w of words) {
trie.insert(w);
}
let ans = '';
for (const w of words) {
if (trie.search(w) && (ans.length < w.length || (ans.length === w.length && w < ans))) {
ans = w;
}
}
return ans;
}type Trie struct {
children [26]*Trie
isEnd bool
}
func (t *Trie) insert(w string) {
node := t
for i := 0; i < len(w); i++ {
idx := w[i] - 'a'
if node.children[idx] == nil {
node.children[idx] = &Trie{}
}
node = node.children[idx]
}
node.isEnd = true
}
func (t *Trie) search(w string) bool {
node := t
for i := 0; i < len(w); i++ {
idx := w[i] - 'a'
if node.children[idx] == nil || !node.children[idx].isEnd {
return false
}
node = node.children[idx]
}
return true
}
func longestWord(words []string) string {
trie := &Trie{}
for _, w := range words {
trie.insert(w)
}
ans := ""
for _, w := range words {
if trie.search(w) && (len(ans) < len(w) || (len(ans) == len(w) && w < ans)) {
ans = w
}
}
return ans
}struct Trie {
children: [Option<Box<Trie>>; 26],
is_end: bool,
}
impl Trie {
fn new() -> Self {
Trie {
children: Default::default(),
is_end: false,
}
}
fn insert(&mut self, w: &str) {
let mut node = self;
for c in w.chars() {
let idx = (c as usize) - ('a' as usize);
if node.children[idx].is_none() {
node.children[idx] = Some(Box::new(Trie::new()));
}
node = node.children[idx].as_mut().unwrap();
}
node.is_end = true;
}
fn search(&self, w: &str) -> bool {
let mut node = self;
for c in w.chars() {
let idx = (c as usize) - ('a' as usize);
if node.children[idx].is_none() || !node.children[idx].as_ref().unwrap().is_end {
return false;
}
node = node.children[idx].as_ref().unwrap();
}
true
}
}
impl Solution {
pub fn longest_word(words: Vec<String>) -> String {
let mut trie = Trie::new();
for w in &words {
trie.insert(w);
}
let mut ans = String::new();
for w in words {
if trie.search(&w) && (ans.len() < w.len() || (ans.len() == w.len() && w < ans)) {
ans = w;
}
}
ans
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Sorting and Set-based Verification | Time complexity: O(N log N + N * M), where sorting and prefix lookups determine the time complexity. Space complexity: O(N * M), owing to the storage in the set for valid words. |
| Trie-based Approach | Time complexity: O(N * M), where creating the Trie and checking word validity both operate over each character of every word. Space complexity: O(N * M) for the Trie data structure. |
| Trie | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sorting + Hash Set Verification | O(n log n) | O(n) | General interview solution. Simple implementation using sorting and fast prefix checks. |
| Trie-based Prefix Validation | O(n * L) | O(n * L) | Useful when many words share prefixes or when demonstrating Trie knowledge. |
Frequently asked questions
Is Longest Word in Dictionary easy or hard?
The problem is rated Medium because it requires recognizing the prefix-building constraint and choosing an efficient data structure. The logic is straightforward once you realize every valid word must have its immediate prefix already validated.
How to solve Longest Word in Dictionary in O(n)?
An O(n * L) solution can be achieved using a Trie. Insert all words into the Trie and ensure every node along a candidate word's path is marked as a complete word. Because each character is processed during insertion and traversal only once, the complexity becomes linear with respect to total characters.
What is the best approach for Longest Word in Dictionary?
The most practical solution uses sorting combined with a hash set. Sort the words lexicographically, then iterate and check whether the prefix of length n-1 exists in a set of valid words. This ensures each word can be built step‑by‑step. The approach runs in O(n log n) time due to sorting and O(n) extra space.
What data structure is used in Longest Word in Dictionary?
Two main data structures are used: a hash set and a Trie. The hash set stores valid words and allows constant-time prefix checks, while the Trie organizes words by shared prefixes and enables efficient prefix validation during traversal.
What is the time complexity of Longest Word in Dictionary?
The common sorting + hash set solution runs in O(n log n) time because the word list must be sorted first. Each word then performs an O(1) average hash lookup for its prefix. A Trie-based approach processes each character once, giving O(n * L) time where L is the average word length.
Longest Word in Dictionary Python or Java solution approach?
In Python or Java, sort the word list and maintain a HashSet (or set in Python) containing buildable words. For each word, check if its prefix word.substring(0, len-1) exists in the set. If it does, add the word and update the best result based on length and lexicographic order.
Is Longest Word in Dictionary asked at Google, Amazon, or Meta?
Prefix-based dictionary problems frequently appear in interviews at companies like Google, Amazon, and Meta. Variations of this problem test understanding of hash sets, prefix validation, and Trie structures. Interviewers often expect the hash set approach first, followed by a discussion of Trie optimization.