# 0720. Longest Word in Dictionary
###### tags: `Leetcode` `Medium` `Trie`
## 思路
先sort 然后建trie
如果是单个字母就直接放进trie里
如果不是的话顺着trie往下走 如果哪里断掉了 说明这个word cannot be built one character at a time by other words in words
所以不能考虑它的长度
## Code

class Solution {
    class TrieNode{
        TrieNode[] children = new TrieNode[26];
    }
    TrieNode root;
    public String longestWord(String[] words) {
        Arrays.sort(words);
        root = new TrieNode();
        int maxLen = 0;
        String ans = "";
        for(String word:words){
            if(insert(word)){
                if(maxLen<word.length()){
                    maxLen = word.length();
                    ans = word;
                }
            }
        }
        return ans;
    }
    private boolean insert(String word){
        if(word.length()==1){
            root.children[word.charAt(0)-'a'] = new TrieNode();
        }
        else{
            TrieNode curr = root;
            for(int i=0; i<word.length()-1; i++){
                if(curr.children[word.charAt(i)-'a']==null) return false;
                curr = curr.children[word.charAt(i)-'a'];
            }
            curr.children[word.charAt(word.length()-1)-'a'] = new TrieNode();
        }
        return true;
    }
}