#720

Medium

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Longest Word in Dictionary

Find the longest word in a dictionary that can be built one character at a time from other words in the dictionary.

Problem Statement

Given a list of words representing an English dictionary, return the longest word that can be built one character at a time, each prefix of the word must also be a word in the list. If there is more than one possible word, return the one with the smallest lexicographical order.

A word can be constructed by successively adding characters to its previous form. If no such word exists, return an empty string.

Examples

Example 1

Input: words = ["w","wo","wor","worl","world"]

Output: "world"

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"

Both "apply" and "apple" can be built from other words in the dictionary. However, "apple" is lexicographically smaller than "apply".

Constraints

1 <= words.length <= 1000
1 <= words[i].length <= 30
words[i] consists of lowercase English letters.

Solution Approach

Array Scanning with Hash Lookup

Iterate through each word in the dictionary and check if all its prefixes exist using a Set. If so, it's a valid candidate. Track the longest word while considering lexicographical order.

Efficient Word Validation

By maintaining a Set of words, checking whether a prefix exists becomes a constant-time operation. This enables the solution to handle the problem efficiently even for larger inputs.

Handling Lexicographical Order

While iterating through the dictionary, if a valid word has the same length as a previously found word, compare them lexicographically and keep the smallest.

Complexity Analysis

Metric	Value
Time	O(\sum w_i)
Space	O(\sum w_i)

Time complexity is O(∑ w_i) due to iterating over all words and checking their prefixes, and space complexity is O(∑ w_i) because of storing words in a Set for fast lookups.

What Interviewers Usually Probe

Evaluate whether the candidate efficiently uses hash sets for prefix checking.
Assess how well the candidate handles lexicographical order when there are multiple valid longest words.
Check if the candidate optimizes for time and space when validating word prefixes.

Common Pitfalls or Variants

Common pitfalls

Failing to use a Set to quickly check word prefixes can result in slower solutions.
Not handling multiple valid words with the same length but different lexicographical orders correctly.
Overlooking edge cases where no valid word can be built from the dictionary.

Follow-up variants

Consider cases where the input list contains a mix of short and long words.
Test the solution against a dictionary with words having the same prefixes but different lengths.
Evaluate performance when all words in the dictionary are valid and can be built from each other.

FAQ

What is the optimal way to check if all prefixes of a word exist in the dictionary?

Use a Set to store words for constant-time lookups, then check each prefix of the word during the iteration.

How do I handle cases where multiple longest words are valid?

Track the lexicographically smallest word when multiple words of the same length are found.

How can I optimize my solution for large inputs?

Ensure the Set lookup is used to validate prefixes and avoid unnecessary repeated iterations over the words.

What should I do if no valid word can be built from the dictionary?

Simply return an empty string in this case.

What is the expected time complexity for this problem?

The time complexity is O(∑ w_i), where w_i is the length of each word. This accounts for checking all prefixes of each word.

terminal

Solution

Solution 1: 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.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

class Trie:
    def __init__(self):
        self.children: List[Optional[Trie]] = [None] * 26
        self.is_end = False

    def insert(self, w: str):
        node = self
        for c in w:
            idx = ord(c) - ord("a")
            if node.children[idx] is None:
                node.children[idx] = Trie()
            node = node.children[idx]
        node.is_end = True

    def search(self, w: str) -> bool:
        node = self
        for c in w:
            idx = ord(c) - ord("a")
            if node.children[idx] is None:
                return False
            node = node.children[idx]
            if not node.is_end:
                return False
        return True


class Solution:
    def longestWord(self, words: List[str]) -> str:
        trie = Trie()
        for w in words:
            trie.insert(w)
        ans = ""
        for w in words:
            if trie.search(w) and (
                len(ans) < len(w) or (len(ans) == len(w) and ans > w)
            ):
                ans = w
        return ans

Continue Practicing

#692 top k frequent words #792 number of matching subsequences #721 accounts merge