[Java] - The easiest to understand trie solution. [100%, Explanation]
We will use Trie, also called Prefix tree, structure to solve the problem.  \nIf you don\'t know what the Trie is, then complete this problem first https://leet
We will use `Trie`, also called `Prefix tree`, structure to solve the problem.  \nIf you don\'t know what the `Trie` is, then complete this problem first https://leetcode.com/problems/implement-trie-prefix-tree/\n\nFirst of all, let\'s define our node of tree:\n\n\tclass TreeNode {\n\t\tTreeNode[] children = new TreeNode[26];\n\t\tString word;\n\n\t\tTreeNode () {}\n\t}\n\nAs said in constraints, words contains lowercase letters only; That\'s why we can simply use array `TreeNode[26]` to store node children. To compute the index we will use next trick - `index = character - \'a\'`.\nWe need to, somehow, check is the node represents a word. So, let\'s store in each `TreeNode` field `word`. If node is representing the word, then value of word will be in the field `word`, otherwise field will be empty.\n\nHow to insert a word into our `Trie`? - Using `current` as pointer of node. If `current` don\'t have `character` in his children, just put new `TreeNode` to `current` children.\nWe have to put word character by character into Tree. There are 2 cases:\n- 1) We already have the character -  just set `current` to `current.children[c - \'a\']`\n- 2) We don\'t have the character yet - put it into `current.children` and then set `current` to `current.children[c - \'a\']`\n\nAt the end of inserting operation we need to take node, represanting the last character of a word, and set it `word` field to whole word.\n\nThe code below insert word into our `Trie`:\n\n\tprivate void insert(String word) {\n\t\tTreeNode current = root;\n\t\tfor (char c : word.toCharArray()) {\n\t\t\tif (current.children[c - \'a\'] == null)\n\t\t\t\tcurrent.children[c - \'a\'] = new TreeNode();\n\t\t\tcurrent = current.children[c - \'a\'];\n\t\t}\n\t\tcurrent.word = word;\n\t}\n\n\nAs we defined our `TreeNode` and `insert` function, let\'s fill it by all words, we have in input:\n\n\tfor (String w : words)\n\t\t\t\tinsert(w);\n\nNow we have all words in our `Trie` and just have to iterate over the whole tree and find the longest word.\nWe will use `Depth-First Search` to iterate over it.\nAs said in the problem defenition, we should build each word `character by character`. It means, if we have character, which isn\'t word - we should stop `DFS` for this branch of our `Trie`.\nIf current `TreeNode` have word - then check is it the longest word, we are looking for.\n\nNext code describes `DFS`, looking for the longest word:\n\n\tprivate void dfs(TreeNode node) {\n\t\tif (node == null)\n\t\t\treturn;\n\n\t\tif (node.word != null) {\n\t\t\tif (node.word.length() > result.length())\n\t\t\t\tresult = node.word;\n\t\t\telse if (node.word.length() == result.length() && node.word.compareTo(result) < 0)\n\t\t\t\tresult = node.word;\n\t\t}\n\n\t\tfor (TreeNode child : node.children)\n\t\t\tif (child != null && child.word != null)\n\t\t\t\tdfs(child);\n\t}\n\nEnjoy ;)\nThe whole solution:\n\n\tclass Solution {\n\t\tprivate TreeNode root;\n\t\tprivate String result = "";\n\n\t\tpublic String longestWord(String[] words) {\n\t\t\troot = new TreeNode();\n\n\t\t\tfor (String w : words)\n\t\t\t\tinsert(w);\n\n\t\t\tdfs(root);\n\n\t\t\treturn result;\n\t\t}\n\n\t\tprivate void dfs(TreeNode node) {\n\t\t\tif (node == null)\n\t\t\t\treturn;\n\n\t\t\tif (node.word != null) {\n\t\t\t\tif (node.word.length() > result.length())\n\t\t\t\t\tresult = node.word;\n\t\t\t\telse if (node.word.length() == result.length() && node.word.compareTo(result) < 0)\n\t\t\t\t\tresult = node.word;\n\t\t\t}\n\n\t\t\tfor (TreeNode child : node.children)\n\t\t\t\tif (child != null && child.word != null)\n\t\t\t\t\tdfs(child);\n\t\t}\n\n\t\tprivate void insert(String word) {\n\t\t\tTreeNode current = root;\n\t\t\tfor (char c : word.toCharArray()) {\n\t\t\t\tif (current.children[c - \'a\'] == null)\n\t\t\t\t\tcurrent.children[c - \'a\'] = new TreeNode();\n\t\t\t\tcurrent = current.children[c - \'a\'];\n\t\t\t}\n\t\t\tcurrent.word = word;\n\t\t}\n\n\t}\n\n\tclass TreeNode {\n\t\tTreeNode[] children = new TreeNode[26];\n\t\tString word;\n\n\t\tTreeNode () {}\n\t}
['Depth-First Search', 'Trie', 'Java']