> For the complete documentation index, see [llms.txt](https://jaywin.gitbook.io/leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://jaywin.gitbook.io/leetcode/solutions/0720-longest-word-in-dictionary.md).

# 0720. Longest Word in Dictionary

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

## Description

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.

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

## ac1: trie

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

        TrieNode root = new TrieNode();
        for (String w : words) build(root, w);

        return search(root);
    }
    private void build(TrieNode root, String word) {
        for (int i = 0; i < word.length(); i++) {
            int pos = word.charAt(i) - 'a';
            if (root.next[pos] == null) root.next[pos] = new TrieNode();
            root = root.next[pos];
        }
        root.word = word;
    }
    private String search(TrieNode root) {
        String res = root.word != null ? root.word : "";
        for (TrieNode t : root.next) {
            if (t == null || t.word == null) continue; // null node or not a word in dict
            String child = search(t);
            if (child.length() > res.length()) res = child;
        }
        return res;
    }
}
class TrieNode {
    TrieNode[] next;
    String word;
    public TrieNode() {
        next = new TrieNode[26];
    }
}
```