We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Longest Word in Dictionary

Difficulty: Medium

Problem Description

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. The word should be built from left to right with each additional character being added to the end of a previous word.

Key Insights

  • We need to identify words that can be constructed character by character from other words in the list.
  • The solution requires sorting the list of words to ensure we can build them from shorter to longer.
  • A set can be used to store valid prefixes to check if a word can be built from existing shorter words.
  • The longest valid word must be returned, with lexicographical order considered in case of ties.

Space and Time Complexity

Time Complexity: O(n log n) for sorting the list of words, where n is the number of words. Checking prefixes takes O(n) on average. Overall, the complexity is dominated by the sorting step.

Space Complexity: O(n) for storing the words in a set.

Solution

To solve this problem, we can follow these steps:

  1. Sort the list of words. This ensures that we can process shorter words before longer ones.
  2. Use a set to keep track of valid prefixes as we build longer words.
  3. Iterate through the sorted list, and for each word, check if all its prefixes (up to the last character) exist in the set.
  4. If a word can be built from its prefixes, add it to the set and check if it is the longest valid word found so far.
  5. Return the longest valid word found, or an empty string if none exists.

Code Solutions

def longestWord(words):
    words.sort()  # Step 1: Sort the words
    word_set = set()  # Step 2: Create a set to store valid prefixes
    longest = ""  # Variable to keep track of the longest word
    
    for word in words:
        # Step 3: Check if the word can be built from its prefixes
        if len(word) == 1 or word[:-1] in word_set:
            word_set.add(word)  # Add the valid word to the set
            # Step 4: Update the longest word if needed
            if len(word) > len(longest) or (len(word) == len(longest) and word < longest):
                longest = word
    
    return longest  # Step 5: Return the longest valid word
← Back to All Questions