# 720. Longest Word in Dictionary

&#x20;[**720. Longest Word in Dictionary**](https://leetcode.com/problems/longest-word-in-dictionary/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]`.

***My Solutions:***

```java
class Solution {
    
    class TrieNode {
        public TrieNode[] children;
        public boolean end;
            
        public TrieNode() {
            this.children = new TrieNode[26];
        }
    }
    
    class Trie {
        
        public TrieNode root;
        
        public Trie() {
            this.root = new TrieNode();
            root.end = true;
        }
        
        public void insert(String s) {
            TrieNode node = root;
            for (char c : s.toCharArray()) {
                if (node.children[c - 'a'] == null) node.children[c - 'a'] = new TrieNode();
                node = node.children[c - 'a'];
            }
            node.end = true;
        }
        
        public boolean search(String s) {
            TrieNode node = root;
            for (char c : s.toCharArray()) {
            
            // !node.end 表示如果在单词中找不到一个字母，直接返回false
                    
                if (node.children[c - 'a'] == null || !node.end) return false;
                node = node.children[c - 'a'];
            }
            return true;
        }
    }
    
    public String longestWord(String[] words) {
        
        Trie t = new Trie();
        for (String word : words) t.insert(word);
        
        String res = "";
        for (String word : words) {
            if (word.length() >= res.length() && t.search(word)) {
                if (word.length() > res.length()) res = word;
                else res = word.compareTo(res) < 0 ? word : res;
            }
        }
        return res;
    }
}
```
