# 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

See: <https://leetcode.com/problems/longest-word-in-dictionary/solution/>

**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

```java
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;
    }
}
```