# 1858. Longest Word With All Prefixes
###### tags: `Leetcode` `Medium` `Trie`
Link: https://leetcode.com/problems/longest-word-with-all-prefixes/
## 思路 $O(MN)$ $O(MN)$ MN是所有word里面的character总数
Trie的一条路径里面如果每个node的isword都是true，就是合格的word，再在合格的word里面找出最长且lexicographically smallest的那个
## Code

class Solution {
    public String longestWord(String[] words) {
        for(String word:words){
            addWord(word);
        }
        String ans = new String();
        for(String word:words){
            if(checkPrefix(word)){
                if(ans.length()<word.length()) ans = word;
                else if(ans.length()==word.length() && word.compareTo(ans)<0) ans = word;
            }
        }
        return ans;
    }
 
    class TrieNode{
        TrieNode[] children = new TrieNode[26];
        boolean isWord = false;
    }
    TrieNode root = new TrieNode();
    private void addWord(String word){
        TrieNode curr = root;
        for(char c:word.toCharArray()){
            if(curr.children[c-'a']==null){
                curr.children[c-'a'] = new TrieNode();
            }
            curr = curr.children[c-'a'];
        }
        curr.isWord = true;
    }
    private boolean checkPrefix(String word){
        TrieNode curr = root;
        for(char c:word.toCharArray()){
            if(curr.children[c-'a']==null || !curr.children[c-'a'].isWord) return false;
            curr = curr.children[c-'a'];
        }
        return true;
    }
}