# 720 Longest Word in Dictionary

## 720. [Longest Word in Dictionary](https://leetcode.com/problems/longest-word-in-dictionary/description/)

## 1. Question

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

## 2. Implementation

**(1) Sorting + Trie**

```java
class Solution {
    class TrieNode {
        char val;
        boolean isWord;
        TrieNode[] childNode;

        public TrieNode(char val) {
            this.val = val;
            childNode = new TrieNode[256];
        }
    }
    public String longestWord(String[] words) {
        if (words == null || words.length == 0) {
            return "";
        }

        Arrays.sort(words);
        String res = "";

        TrieNode root = new TrieNode(' ');

        for (String word : words) {
            TrieNode curNode = root;
            for (int i = 0; i < word.length(); i++) {
                char c = word.charAt(i);
                if (curNode.childNode[c] == null && i < word.length() - 1) {
                    break;
                }
                else if (curNode.childNode[c] == null) {
                    curNode.childNode[c] = new TrieNode(c);
                }
                curNode = curNode.childNode[c];
                if (i == word.length() - 1) {
                    res = res.length() < word.length()? word : res;
                }
            }
        }
        return res;
    }
}
```

**(2) Sorting + Hash Set**

```java
class Solution {
    public String longestWord(String[] words) {
        if (words == null || words.length == 0) {
            return "";
        }

        String res = "";

        Arrays.sort(words);
        Set<String> set = new HashSet<>();

        for (String word : words) {
            if (word.length() == 1 || set.contains(word.substring(0, word.length() - 1))) {
                if (word.length() > res.length()) {
                    res = word;
                }
                set.add(word);
            }
        }
        return res;
    }
}
```

## 3. Time & Space Complexity

Sorting + Trie: 时间复杂度O(nlogn + nL), n是word的个数，L是word的平均长度， 空间复杂度O(nL)

Sorting + Hash Set: 时间复杂度O(nlogn), 空间复杂度O(n)
