Java Solution with Trie + BFS
The idea is simple. First, we construct a trie for the dictionary. Then we traverse the whole trie to get the longest word.\nWe could choose DFS or BFS to achie
The idea is simple. First, we construct a trie for the dictionary. Then we traverse the whole trie to get the longest word.\nWe could choose DFS or BFS to achieve the trie traversal. Here, I leverage the property of BFS that it would get a layer of a tree from top to down at one time. Therefore, every time we get a new candidate word, we could replace the old one. Also, I scan the children of a trie node from last to first because we want the word with the smallest lexicographical order.\n```\nclass Solution {\n    class TrieNode {\n        TrieNode[] children;\n        boolean isWord;\n        String word;\n        \n        public TrieNode() {\n            children = new TrieNode[26];\n        }\n    }\n    \n    class Trie {\n        private TrieNode root;\n        \n        public Trie() {\n            root = new TrieNode();\n        }\n        \n        public void insert(String word) {\n            TrieNode node = root;\n            for (int i = 0; i < word.length(); i++) {\n                int idx = word.charAt(i) - 'a';\n                if (node.children[idx] == null) {\n                    node.children[idx] = new TrieNode();\n                }\n                node = node.children[idx];\n            }\n            node.isWord = true;\n            node.word = word;\n        }\n        \n        public String findLongestWord() {\n            String result = null;\n            Queue<TrieNode> queue = new LinkedList<>();\n            queue.offer(root);\n            while (!queue.isEmpty()) {\n                int size = queue.size();\n                for (int i = 0; i < size; i++) {\n                    TrieNode node = queue.poll();\n                    for (int j = 25; j >= 0; j--) {\n                        if (node.children[j] != null && node.children[j].isWord) {\n                            result = node.children[j].word;\n                            queue.offer(node.children[j]);\n                        }\n                    }\n                }\n            }\n            return result;\n        }\n    }\n    \n    public String longestWord(String[] words) {\n        Trie trie = new Trie();\n        for (String word : words) {\n            trie.insert(word);\n        }\n        \n        return trie.findLongestWord();\n    }\n}\n```
[]