Java Trie without DFS/BFS
Lots of solutions build the Trie and use DFS/BFS to find the deepest node.\nBut actually, we can just get the longest word while building the Trie.\n\nHow to so
Lots of solutions build the Trie and use DFS/BFS to find the deepest node.\nBut actually, we can just get the longest word while building the Trie.\n\n**How to solve without DFS/BFS?**\nThe idea is using a variable `maxString` to store the longest word.\nIf it\'s the last character, we compare the word length with `maxString` and update  `maxString` if needed.\nAt the end, we can just return the `maxString`.\n\n**What if two words length are the same?**\nWe sort the words first so it gurantees that we meet the string by lexicographical order.\nTherefore, the first word to be updated as `maxStrinig` is the lexicographically smallest word. No need to modify our algorithm.\ne.g. ["a",  "ap", "app", "appl", "apple", "apply"]\nWhile building the Trie: `"a"->"p"->"p"->"l"->"e"`\nHere `maxString` is updated to "apple"\nAnd while inserting "apply": `"a"->"p"->"p"->"l"->"y"`, here `maxString` will not be updated\n                                                                          \n**Special operation for this problem:**\nWords are sorted. We are inserting a `word` into Trie, and we are now traversing to `word[i]` in the Trie and begin to build for `word[i+1]`, if `word[i]` is not the last character (`i < word.length() - 1`) and the Trie node  `word[i+1]` doesn\'t already exist. This situation means we cannot build for `word`\ne.g. words: ["w", "wo", "wor", "world"] \nAfter inserting "w", "wo" and "wor"\nWhen inserting "world", we traverse the Trie: `"w" -> "o" -> "r"` and here normally we are going to insert `"l"` for "world", but not for this problem.\nSince there\'s no `"l"` node for `"r"`, it means that we cannot build "world" because we lack of the word `"worl"`. "world" is defintely not the answer, so we can just stop insertion.\n\n```\nclass Solution {\n    public String longestWord(String[] words) {\n        if (words == null || words.length == 0)\n            return "";\n        Trie head = new Trie();\n        Arrays.sort(words);\n        for (String word : words)\n            head.insert(word);\n        return head.maxString;\n    }\n    public class Trie {\n        public String maxString = "";\n        public Trie[] children = new Trie[26];\n        public void insert(String s) {\n            Trie cur = this;\n            char[] chs = s.toCharArray();\n            for (int i = 0; i < chs.length; i++) {\n                int idx = chs[i] - \'a\';\n                if (cur.children[idx] != null) {\n                    cur = cur.children[idx];\n                } else {\n                    if (i < s.length() - 1) //special operation (refer to explaination above)\n                        return;\n                    cur.children[idx] = new Trie();\n                    cur = cur.children[idx];\n                    if (s.length() > maxString.length())\n                        maxString = s;\n                }\n            }\n        }\n    }\n}\n```
[]