Longest Word in Dictionary

The problem is to find the longest word in a given dictionary that can be constructed one character at a time by other words in the dictionary. If there are multiple words of the same length, we need to return the one that comes first lexicographically.

Here’s a step-by-step guide to solve this problem:

1. Sort the words and add them to a set

First, we sort the words so that we deal with shorter words first, and add all words to a set for quick lookup.

2. Check each word

Iterate through the sorted words and check if each prefix of the word exists in the set. We can use a variable to keep track of the current longest word that can be constructed.

3. Return the result

Return the longest word that can be constructed.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution:
    def longestWord(self, words: List[str]) -> str:
        word_set, longest = set(words), ""

        # Sort words to consider shorter words first
        words.sort()

        for word in words:
            if len(word) > len(longest) or (len(word) == len(longest) and word < longest):
                if all(word[:k] in word_set for k in range(1, len(word))):
                    longest = word

        return longest

Insights

• Sorting: Sorting ensures that shorter words are considered first, so they can act as building blocks for longer words.
• Prefix Checking: By checking all prefixes of a word, we ensure that it can be constructed one character at a time.
• Lexicographical Order: Since the words are sorted, we naturally consider lexicographically smaller words first.
• Time Complexity: Sorting the words takes (O(n \log n)) time, where (n) is the total number of characters across all words. Checking prefixes takes (O(n)) time. So, the overall time complexity is (O(n \log n)).
• Space Complexity: Storing the words in a set takes (O(n)) space.

This solution efficiently finds the longest word that can be constructed from other words in the dictionary, considering both length and lexicographical order.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

def longest_word(words)
  output = ''
  words = words.sort
    
  set = Set.new
    
  words.each do |word|
    prefix_found = set.include?(word[0, word.size-1])

    if word.size == 1 || prefix_found
      if word.size > output.size
        output = word
      end
      set.add(word)
    end
  end
  
  return output
end

title: Longest Word in Dictionary excerpt: Checking prefixes to construct the longest word in Dictionary tags: prefix

Solution

I modified the solution that I found online to make it easier to follow the tracing of calls in a debugger. The code is concise and elegant.

 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

require 'set'

def longest_word(words)
  output = ''
  
  # Sort alphabetically
  words = words.sort
    
  set = Set.new
    
  words.each do |word|
    prefix = word[0, word.size-1]
    found = set.include?(prefix)

    if word.size == 1 || found
      # Pick only bigger words to update the result
      if word.size > output.size
        output = word
      end
      # remember the words we have seen so far
      set.add(word)
    end
  end
  
  return output
end

words = ["yo","ew","fc","zrc","yodn","fcm","qm","qmo","fcmz","z","ewq","yod","ewqz","y"]

p longest_word(words)

Run this through the debugger to understand how to code works.