Domain 1EasyCORE

Longest Word in Dictionary

The problem requires finding the longest word in a given dictionary that can be constructed by adding one character at a time from other words in the dictionary. If multiple such words exist, return the lexicographically smallest one. The input is an array of strings representing the dictionary, and the output should be a single string.

Domain: Easy•Updated: 2026-08-31
#Algorithms#LeetCode#qwen2.5-coder:14b#Hash Table#Trie

720. Longest Word in Dictionary

Model: qwen2.5-coder:14b
Topics: Hash Table,Trie
FAANG asked: 1
Acceptance rate: 49.4%


Problem Breakdown

The problem requires finding the longest word in a given dictionary that can be constructed by adding one character at a time from other words in the dictionary. If multiple such words exist, return the lexicographically smallest one. The input is an array of strings representing the dictionary, and the output should be a single string.

Inputs:

  • words: An array of strings where each string consists of lowercase English letters.

Outputs:

  • A single string that is the longest word meeting the criteria. If there are multiple such words, return the lexicographically smallest one.

Implicit Constraints or Edge Cases:

  • The dictionary can be empty.
  • Words may contain duplicate characters.
  • The dictionary might have multiple valid answers of the same length.

Intuition

A brute-force approach would involve checking each word to see if all its prefixes are in the dictionary. This would result in a time complexity of O(n * m^2), where n is the number of words and m is the average length of the words, due to repeated substring checks.

The key insight is to use a data structure that allows efficient prefix checking, such as a Trie (prefix tree). By inserting all words into a Trie, we can traverse the Trie to find the longest word that can be built one character at a time. This approach reduces the complexity of prefix checks to O(1) on average.

Approach

  1. Insert Words into Trie: Traverse each word in the dictionary and insert it into a Trie. Each node in the Trie represents a character, and the path from the root to a node represents a prefix.
  2. Find Longest Word: Perform a depth-first search (DFS) on the Trie starting from the root. During the DFS, keep track of the current word being formed. If a node is marked as the end of a word and all its prefixes are also words in the dictionary, continue the DFS. Keep updating the longest valid word found.
  3. Return Result: After traversing the entire Trie, return the longest word that can be built one character at a time.

Complexity Analysis

  • Time Complexity: O(n * m), where n is the number of words and m is the average length of the words. Inserting each word into the Trie takes O(m) time, and traversing the Trie also takes O(n * m) time.
  • Space Complexity: O(n * m), as we store all characters of all words in the Trie.

Solution

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end_of_word = False

class Trie:
    def __init__(self):
        self.root = TrieNode()
    
    def insert(self, word):
        node = self.root
        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
        node.is_end_of_word = True

class Solution:
    def longestWord(self, words: List[str]) -> str:
        trie = Trie()
        for word in words:
            trie.insert(word)
        
        self.longest = ""
        
        def dfs(node, path):
            if not node.is_end_of_word:
                return
            if len(path) > len(self.longest):
                self.longest = ''.join(path)
            elif len(path) == len(self.longest) and ''.join(path) < self.longest:
                self.longest = ''.join(path)
            
            for char, child in sorted(node.children.items()):
                dfs(child, path + [char])
        
        dfs(trie.root, [])
        return self.longest

Edge Cases Handled

  • Empty Dictionary: If the input dictionary is empty, the function returns an empty string.
  • Single Word: If there’s only one word in the dictionary and it can be built character by character (e.g., [“a”]), it returns that word.
  • Multiple Valid Words: If multiple words are of the same length and can be built character by character, it returns the lexicographically smallest one.