Longest Word in Dictionary

Longest Word in Dictionary: 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.

Note that the word should be built from left to right with each additional character being added to the end of a previous word.

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".

Constraints:

1 <= words.length <= 1000
1 <= words[i].length <= 30
words[i] consists of lowercase English letter.

Try this Problem on your own or check similar problems:

Solution:

Java
JavaScript
Python
C++

class Solution {
  class Trie {
      private class TrieNode{
          TrieNode[] children;
          boolean isWord = false;
          String word;
          public TrieNode(){
              children = new TrieNode[26];
          }
      }

      TrieNode root;
      public Trie() {
          root = new TrieNode();
      }

      public void insert(String word) {
        TrieNode iter = root;
        for(int i = 0; i < word.length(); ++i){
          char letter = word.charAt(i);
          if(iter.children[letter - 'a'] == null){
              iter.children[letter - 'a'] = new TrieNode();
          }
          iter = iter.children[letter - 'a'];
        }
        iter.isWord = true;
        iter.word = word;
      }


      public String longestWord() {
          String result = "";
          Queue<TrieNode> q = new LinkedList<>();
          q.offer(root);
          while (!q.isEmpty()) {
              int size = q.size();
              while(size-->0){
                TrieNode node = q.poll();
                for (int j = 25; j >= 0; j--) {
                  if (node.children[j] != null && node.children[j].isWord) {
                      result = node.children[j].word;
                      q.add(node.children[j]);
                  }
                }
              }
          }
          return result;
      }
  }

  public String longestWord(String[] words) {
      Trie trie = new Trie();
      for(String word: words){
          trie.insert(word);
      }
      return trie.longestWord();
  }
}

/**
 * @param {string[]} words
 * @return {string}
 */
var longestWord = function (words) {
  const trie = new Trie();
  for (const word of words) {
    trie.insert(word);
  }
  return trie.longestWord();
};

class Trie {
  constructor() {
    this.root = new TrieNode();
  }

  insert(word) {
    let iter = this.root;
    for (let i = 0; i < word.length; ++i) {
      const letter = word.charAt(i);
      if (iter.children[letter.charCodeAt(0) - 97] === null) {
        iter.children[letter.charCodeAt(0) - 97] = new TrieNode();
      }
      iter = iter.children[letter.charCodeAt(0) - 97];
    }
    iter.isWord = true;
    iter.word = word;
  }

  longestWord() {
    let result = "";
    const q = [this.root];
    while (q.length > 0) {
      const size = q.length;
      for (let i = 0; i < size; i++) {
        const node = q.shift();
        for (let j = 25; j >= 0; j--) {
          if (node.children[j] && node.children[j].isWord) {
            result = node.children[j].word;
            q.push(node.children[j]);
          }
        }
      }
    }
    return result;
  }
}

class TrieNode {
  constructor() {
    this.children = Array(26).fill(null);
    this.isWord = false;
    this.word = "";
  }
}

class Solution:
    class Trie:
      class TrieNode:
          def __init__(self):
              self.children = [None] * 26
              self.isWord = False
              self.word = ''

      def __init__(self):
          self.root = self.TrieNode()

      def insert(self, word):
          iter = self.root
          for letter in word:
              if not iter.children[ord(letter) - ord('a')]:
                  iter.children[ord(letter) - ord('a')] = self.TrieNode()
              iter = iter.children[ord(letter) - ord('a')]
          iter.isWord = True
          iter.word = word

      def longestWord(self):
          result = ''
          q = [self.root]
          while q:
              size = len(q)
              for _ in range(size):
                  node = q.pop(0)
                  for j in range(25, -1, -1):
                      if node.children[j] and node.children[j].isWord:
                          result = node.children[j].word
                          q.append(node.children[j])
          return result

    def longestWord(self, words: List[str]) -> str:
        trie = self.Trie()
        for word in words:
            trie.insert(word)
        return trie.longestWord()

class Solution {
private:
  class TrieNode {
  public:
      vector<TrieNode*> children;
      bool isWord;
      string word;

      TrieNode() {
          children = vector<TrieNode*>(26, nullptr);
          isWord = false;
      }
  };

  class Trie {
  public:
      TrieNode* root;

      Trie() {
          root = new TrieNode();
      }

      void insert(string word) {
          TrieNode* iter = root;
          for (char letter : word) {
              if (!iter->children[letter - 'a']) {
                  iter->children[letter - 'a'] = new TrieNode();
              }
              iter = iter->children[letter - 'a'];
          }
          iter->isWord = true;
          iter->word = word;
      }

      string longestWord() {
          string result = "";
          queue<TrieNode*> q;
          q.push(root);
          while (!q.empty()) {
              int size = q.size();
              while (size-- > 0) {
                  TrieNode* node = q.front();
                  q.pop();
                  for (int j = 25; j >= 0; j--) {
                      if (node->children[j] && node->children[j]->isWord) {
                          result = node->children[j]->word;
                          q.push(node->children[j]);
                      }
                  }
              }
          }
          return result;
      }
  };
public:
    string longestWord(vector<string>& words) {
        Trie trie;
        for (string word : words) {
            trie.insert(word);
        }
        return trie.longestWord();
    }
};

Time/Space Complexity:

Time Complexity: O(sum(w))
Space Complexity: O(sum(w))

Explanation:

We could use a set and put all the words from the input array to it, and for each word check if all of it's prefixes are present in the set, but since we're working with prefixes natural choice would be to build a trie, insert every word into trie and then do a modified BFS approach to find the longest word. We utilize the implementation we did in Implement Trie (Prefix Tree) without the search function and for insert we have only a minor modification since we're holding the exact word for each node that represents the end of that word. Since we do bfs in reverse order on the children we can be sure that the result would contain the longest word (deepest level) but also the one with smallest lexicographical order (since the last node which is checked is the node with smallest letter in lexicographical sense, for example 'a'). To search and build the trie we will spend time and space complexity corresponding to the sum of lengths of all words.

Example 1:​

Example 2:​

Constraints:​

Solution:​

Time/Space Complexity:​