Kotlin fast Trie solution explained
To solve this challenge using Trie data structure is the most appropriate way. I mean, let\'s look at the challenge description again:\n"Design a data structure
To solve this challenge using Trie data structure is the most appropriate way. I mean, let\'s look at the challenge description again:\n"Design a data structure that supports adding new words and finding if a string matches any previously added string."\n\nIsn\'t it just a definition of Trie? It just looks like challenge author asked us to implement Trie without actually asking us to implement Trie. So Trie it is. Now, if you are not familiar with the Trie data structure yet, let\'s dive into it for a minute.\n\nThe trie data structure (or prefix tree) is very interesting data structure for storing strings (or actually any other elements that you can split into atomic parts. numbers, for example, can be split into digits). It works as follows:\n\n1. We start with an empty root node\n![image](https://assets.leetcode.com/users/images/8d173b62-ca0e-43da-b876-42aff1e2d6e4_1643352804.2674875.png)\n\n2. We can insert some string into the tree by splitting it into atomic elements - chars. Let\'s insert the word `bad` into our trie. We split it into `b`, `a`, and `d` and link `b` to the root node, `a` to the `b` node and `d` to the `a` node. We also mark node `d` as a "word" meaning that there is a word ending at this node.\n\n![image](https://assets.leetcode.com/users/images/8aef38a3-2a08-4131-af9e-f4e9d6d3aeab_1643353095.4774163.png)\n\n3. Now we can check that our trie contains word `bad`. We split the word into characters again and first check that the root node has child with value  `b`, `b` node has a child with value `a`, and finally `a` node has a child with value `d` and also `d` is the end of the word. Note that there is no words `b` or `ba` in our trie, because nodes `b` and `a` are not marked as words.\n\n4. Let\'s add some other words to the trie. We will add words `badland`, `bass`, `dog` and `bus` into the trie:\n\t4.1. Adding `badland`: root already has child with value `b`, so we just move to node `b`. `b` already has child `a` and `a` already has child `d` so we move to `d` the same way. Now `d` has not a child with value `l` so we create new node `l`, link it to `d` and move to node `l`. Same situation appears for characters `a`, `n` and `d`. Finally, we mark `d` as a word.\n\t4.2. Adding `bass`: we move to the node `root -> b -> a` same way as we did for word `badland`, now node `a` doesn\'t have child with value `s`, so we create new node and move to it. Same for the second `s`.\n\t4.3. I suppose you can figure out how to add other words using the same logic.\n\n![image](https://assets.leetcode.com/users/images/16d70bdd-fc2f-4597-87e4-718de885668b_1643353934.8150754.png)\n\nSo, the trie we just described is already looks like the solution to the challenge. Except one thing: we need to deal with `.` cahracter. When we have any other character we can just check if current node has a child with this value. But for `.` we have to check all the children for this node, so search will be not iterative, but recursive. Modified version of trie will still work as a simple trie for strings without `.` characters and for `.` it will recursively split between subtrees. Below is the solution code. We just need to implement the `Trie` class and funcions `addWord` and `search` just directly coresspond to `Trie` methods.\n\n```\nclass WordDictionary() {\n    \n    private class Trie {\n        private val root = Node(\'.\')\n        private class Node(val value: Char, val children: Array<Node?> = Array<Node?>(26) { null }, var isWord: Boolean = false)\n        \n        fun insert(word: String) {\n            var currNode = root\n            for (char in word) {\n\t\t\t\t// If child node doesn\'t yet exist, create one\n                if (currNode.children[char - \'a\'] == null) currNode.children[char - \'a\'] = Node(char)\n\t\t\t\t// Move to child node\n                currNode = currNode.children[char - \'a\']!!\n            }\n\t\t\t\n\t\t\t// When reached the end of the word, mark the node as a word\n            currNode.isWord = true\n        }\n        \n\t\t// Recursive search\n        private fun _contains(node: Node, word: String, index: Int): Boolean {\n            if (index == word.length - 1) {\n                if (word[index] == \'.\') return node.children.any { it != null && it.isWord }\n                else return node.children[word[index] - \'a\']?.isWord ?: false\n            }\n            \n            if (word[index] == \'.\') {\n                for (n in node.children) {\n                    if (n == null) continue\n\t\t\t\t\t// Here we recursively split between subtrees\n                    if (_contains(n!!, word, index + 1)) return true\n                }\n                return false\n            } else {\n                if (node.children[word[index] - \'a\'] == null) return false\n                return _contains(node.children[word[index] - \'a\']!!, word, index + 1)\n            }\n            \n            return false\n        }\n        \n        fun contains(word: String): Boolean {\n            return _contains(root, word, 0)\n        }\n    }\n\n    private val trie = Trie()\n    \n    fun addWord(word: String) {\n        trie.insert(word)\n    }\n\n    fun search(word: String): Boolean {\n        return trie.contains(word)\n    }\n\n}\n\n```
['Trie', 'Kotlin']