720. Longest Word in Dictionary.java

//1. HashSet (先sort)
class Solution {
    public String longestWord(String[] words) {
        Arrays.sort(words);
        Set<String> built = new HashSet<String>();
        String res = "";
        for (String w : words) {
            if (w.length() == 1 || built.contains(w.substring(0, w.length() - 1))) {
                res = w.length() > res.length() ? w : res;
                built.add(w);
            }
        }
        return res;
    }
}
//2. Trie (先sort)
class Solution {
    class TrieNode{
        public char val;
        public TrieNode[] hash;
        public TrieNode(){
            this.val='\u0000';
            this.hash=new TrieNode[26];
        }
        public TrieNode(char c){
            this.val=c;
            this.hash=new TrieNode[26];
        }
    }
    public String longestWord(String[] words) {
        TrieNode root=new TrieNode();
        Arrays.sort(words);
        String res="";
        for(String word:words){
            TrieNode curr=root;
            for(int i=0;i<word.length();i++){
                if(curr.hash[word.charAt(i)-'a']==null && i<word.length()-1)
                    break;
                if(curr.hash[word.charAt(i)-'a']==null){
                    TrieNode temp=new TrieNode(word.charAt(i));
                    curr.hash[word.charAt(i)-'a']=temp;
                }
                curr=curr.hash[word.charAt(i)-'a'];
                if(i==word.length()-1)
                    res= res.length() < word.length()? word : res;
            }
        }
        return res;
    }
}