algoadvance

Given an array of strings words representing an English Dictionary, return the longest word in the dictionary 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.

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, but "apple" is lexicographically smaller.

Constraints:

Clarifying Questions

  1. Are there any duplicate words in the input array words?
  2. Should we consider any specific conditions regarding the order of words?

Strategy

  1. Sort the Words:
    • First, sort the words array. This automatically ensures that if two words have the same length, they will be ordered lexicographically.
  2. Set for Fast Lookup:
    • Use a set to store and quickly check if a word can be built from other words one character at a time.
  3. Iterate and Build:
    • Initialize an empty string for the result.
    • Iterate through each word in the sorted list:
      • For each word that has all its prefixes in the set, check if it can become the new longest word.
      • Update the result accordingly.
      • Add the current word to the set for further checks.
  4. Output the Longest Word.

Code

def longestWord(words):
    words.sort()
    word_set = set([""])
    longest_word = ""
    
    for word in words:
        if word[:-1] in word_set:
            word_set.add(word)
            if len(word) > len(longest_word):
                longest_word = word
    
    return longest_word

# Example usage:
words1 = ["w", "wo", "wor", "worl", "world"]
words2 = ["a", "banana", "app", "appl", "ap", "apply", "apple"]

print(longestWord(words1))  # Output: "world"
print(longestWord(words2))  # Output: "apple"

Time Complexity

  1. Sorting: O(n log n) where n is the number of words in the words list.
  2. Iteration: O(n * k) where k is the average length of the words (inserting and checking in a set operates on average O(1) time).

The total time complexity is O(n log n + n * k) which is efficient given the constraints.

Try our interview co-pilot at AlgoAdvance.com