# Longest Word in Dictionary

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]`.

## Analysis

Trie + Depth-First Search

Intuition

As prefixes of strings are involved, this is usually a natural fit for a trie (a prefix tree.)

Algorithm

Put every word in a trie, then depth-first-search from the start of the trie, only searching nodes that ended a word. Every node found (except the root, which is a special case) then represents a word with all it's prefixes present. We take the best such word.

In Python, we showcase a method using defaultdict, while in Java, we stick to a more general object-oriented approach.

## Solution

``````class Solution {
public String longestWord(String[] words) {
Trie trie = new Trie();
for (String word : words) {
trie.insert(word);
}
return dfs(trie.getRoot());
}
String dfs(TrieNode root) {
String longest = "";
Stack<TrieNode> stack = new Stack();
stack.push(root);
while (!stack.isEmpty()) {
TrieNode node = stack.pop();
if (node == null) continue;
if (node.isEnd == true || node == root) {
if (node != root) {
if (node.word.length() > longest.length() ||
(node.word.length() == longest.length() && node.word.compareTo(longest) < 0)) {
longest = node.word;
}
}
for (TrieNode child: node.children) {
stack.push(child);
}
}
}
return longest;
}
}

class Trie {
TrieNode root;
public Trie() {
root = new TrieNode();
}
public void insert(String word) {
TrieNode node = root;
char[] charArray = word.toCharArray();
for (char ch : charArray) {
if (!node.contains(ch)) {
node.put(ch, new TrieNode());
}
node = node.get(ch);
}
node.isEnd = true;
node.word = word;
}

public TrieNode getRoot() {
return root;
}
}
class TrieNode {
TrieNode[] children;
boolean isEnd;
String word;
public TrieNode () {
children = new TrieNode[26];
}
boolean contains(char ch) {
return children[ch - 'a'] != null;
}
TrieNode get(char ch) {
return children[ch - 'a'];
}
void put(char ch, TrieNode node) {
children[ch - 'a'] = node;
}
}
``````