Longest Word in Dictionary

Patrick Leaton
Published: April 18, 2021, 8:01 p.m.
Problem Description

Given a list of strings words representing an English Dictionary, find 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.

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. However, "apple" is lexicographically smaller than "apply".

 

Note:

  • All the strings in the input will only contain lowercase letters.
  • The length of words will be in the range [1, 1000].
  • The length of words[i] will be in the range [1, 30].

 

Description taken from https://leetcode.com/problems/longest-word-in-dictionary/.

Problem Solution

#Trie:O(M) Time, O(M) Space where M is Key Length
#DFS:O(H) Time, O(N) Space, where H is Height and N is Stack
class Solution:
    def longestWord(self, words: List[str]) -> str:
        Trie = lambda: collections.defaultdict(Trie)
        trie = Trie()
        is_end = True
       
        for i, word in enumerate(words):
            curr_node = trie
            for char in word:
                curr_node = curr_node[char]
            curr_node[is_end] = i
           
        stack = list(trie.values())
        output = ""
        while stack:
            node = stack.pop()
            if is_end in node:
                word = words[node[is_end]]
                if len(word) > len(output) or \
                   len(word) == len(output) and word < output:
                    output = word
                for char in node:
                    if char != is_end:
                        stack.append(node[char])
        return output

Problem Explanation

This problem is asking for the longest suffix built from common prefixes.  

When we see that, it typically means we can use a Prefix Tree, also known as a Trie, to get the optimal solution.  A Trie is perfect for these kinds of problems because prefixes are shared within Tries so we will be able to search them in linear time instead of quadratic.

In Python, we can use a default dictionary to implement our Trie.  We will define it and instantiate it here.

        Trie = lambda: collections.defaultdict(Trie)
        trie = Trie()

 

We will also have a boolean variable, is_end.  We will use this to create nodes within our Trie that will signify a stopping point in traversals and also indicate complete words.

        is_end = True

 

We will then enumerate through the words to traverse each word while also having a counter for the indices.  

Let's also create a current node pointer and set it to the root of the Trie.

        for i, word in enumerate(words):
            curr_node = trie

 

As we are traversing the words list, we will also want to traverse the characters within each word.  We will do this by using an inner loop.

For each character in the word we are traversing, we will push the character into our Trie and iterate to it.

            for char in word:
                curr_node = curr_node[char]

 

Once we have pushed every character into the Trie, we will add an ending node set to the index of the current word from our input list.

            curr_node[is_end] = i

 

When we have pushed each character from our words into the Trie, we will perform a DFS to get the longest word.

We will set the stack to the values of the Trie and initialize our output string.

        stack = list(trie.values())
        output = ""

 

While the stack still has values left to pop, our loop will continue to run for our DFS.

        while stack:

 

During each iteration, we will pop a node off of our stack.

If we have an ending node as a child then that means that we have a complete word.

We will use the ending node's index value as the lookup value for our input array to get which word we'd like to test as the longest.

            curr = stack.pop()
            if is_end in curr:
                word = words[curr[is_end]]

 

If the length of the word is greater than our current output string, or if the lengths are the same but the word is less lexicographically, then we will make the word our new output.

                if len(word) > len(output) or \
                   len(word) == len(output) and word < output:
                    output = word

 

Afterward, we will push each of the node's children nodes onto the stack, not including the ending node of the current node.

                for char in node:
                    if char != is_end:
                        stack.append(node[char])

 

Once we have our longest word, we will return it.

        return output