720. Longest Word in Dictionary

Version #1 Trie + DFS
因为只有length 比当前的max大才会Update，所以保证了当有不只一个max的时候，返回的是 smallest lexicographical order

91.21 %
// Time O(n*l) Space O(n*l) -> n:possible words count, l:average word length
class Solution {
    class TrieNode {
    TrieNode[] children;
    boolean isWord;
    public TrieNode() {
        children = new TrieNode[26];
    }
}
class Trie {
    TrieNode root;
    public Trie(String[] words) {
        root = new TrieNode();
        for (String word : words) {
            this.insert(word);
        }
    }
    public void insert(String word) {
        TrieNode curr = root;
        for (int i = 0; i < word.length(); i++) {
            int index = word.charAt(i) - 'a';
            if (curr.children[index] == null) {
                curr.children[index] = new TrieNode();
            }
            curr = curr.children[index];
        }
        curr.isWord = true;
    }
}
    public String longestWord(String[] words) {
        if (words == null || words.length == 0) return "";
        Trie trie = new Trie(words);
        String[] result = new String[]{""};
        dfs(trie.root, result, new StringBuilder());
        return result[0];
    }
    private void dfs(TrieNode currNode, String[] result, StringBuilder sb) {
        TrieNode[] children = currNode.children;
        boolean flag = false;
        for (int i = 0; i < children.length; i++) {
            if (children[i] != null && children[i].isWord) {
                flag = true;
                sb.append((char)('a' + i));
                dfs(children[i], result, sb);
                sb.deleteCharAt(sb.length() - 1);
            }
        }
        if (!flag && sb.length() > result[0].length()) {
            result[0] = sb.toString();
        }
    }
 
}

Version #2 HashSet

二刷
class Solution {
    public String longestWord(String[] words) {
        Arrays.sort(words);
        Set<String> set = new HashSet<>();
        String result = "";
        for (String word : words) {
            if (word.length() == 1 || set.contains(word.substring(0, word.length() - 1))) {
                set.add(word);
                if (word.length() > result.length()) {
                    result = word;
                }
            }
        }
        return result;
    }
}

一刷
 60.70 % 
// Time O(nlogn) Space O(n*l)
class Solution {
    public String longestWord(String[] words) {
        if (words == null || words.length == 0) return "";
        Arrays.sort(words);
        Set<String> dict = new HashSet<>();
        String result = "";
        for (String word : words) {
            if (word.length() == 1 || dict.contains(word.substring(0, word.length() - 1))) {
                dict.add(word);
                if (word.length() > result.length()) result = word;
            }
        }
        return result;
    }
}