Skip to main content

< Back to Data Structures and Algorithms

LeetCode 720 · Strings

Longest Word in Dictionary

The longest word that can be built a letter at a time from other words in the list, checked in sorted order.

Step through it

Examples
Edge cases
words
  1. "a"0
  2. "banana"1
  3. "app"2
  4. "appl"3
  5. "ap"4
  6. "apply"5
  7. "apple"6

Step 0 of 21

Output

Running… play or step to the end.

The code

/**
 * Find the longest word within the given array, of which, all characters before
 * the last character in the word exist as an entity within the array.
 * If multiple words of the same length exist, only return the word with the 
 * smallest lexicograpgical order (eg. show 'c' if 'c','d','e').
 *
 * For example: ["w", "wo", "wor", "worl", "world"] = "world".
 *              ["a","banana","app","appl","ap","apply","apple"] = "apple"
 *              ^ - Both 'apple' and 'apply' work, so return 'apple' (e < y).
 * @param {string[]} words
 * @return {string}
 */
 const longestWord = words => {
  // Stores the words we've encountered.
  const dict = {}
  // Will store the result if we find one.
  let result = ""
  
  // Sort the list of words, to ensure we encounter substrings of larger words first.
  words.sort()
  
  // Iterate over each word.
  words.forEach(word => {
      /* If the word is only one character OR 
         a sub-string of the word, minus the last character, exists within the dictionary */
      if (word.length === 1 ||
          dict[word.substring(0, word.length-1)]
      ) {
          // The word is longer than the current result.
          if (word.length > result.length) {
              // Set the new result to the current word.
              result = word
          }
          
          // Save the current word into the dictionary.
          dict[word] = word
      }
  })
  
  // Found the longest valid word.
  return result
}

View it on GitHub (opens in a new tab)