Trie explained line by line C++
I tried to explain everything that goes through my mind while I\'m solving this problem, please if that helped you, upvote my discuss, if not, please tell me wh
I tried to explain everything that goes through my mind while I\'m solving this problem, please if that helped you, upvote my discuss, if not, please tell me what I should improve.\n\nEdit: Sometimes it can give TLE, if that happen, try to submit again.\n```\n// First we need to create our TrieNode class\nclass TrieNode\n{\npublic:\n    bool is_leaf;\n\t // as we only need to store lower case english letters, we only need an array with 26 size\n\t // it\'s a good trick to use when we need to store only letters, because we can do it with O(1) in space for each node\n\t // so, we have a linked list, where which node will store only a character.\n    TrieNode* children[26];\n    TrieNode()\n    {\n        is_leaf = false; // it\'ll be used to define if you get the word or not\n\t\t// because if you get is_leaf = true, it means that you got all the word\n\t\t\n\t\t// all children will be initialize being 0\n\t\t// it\'s the same as use a loop, like: for (int i = 0; i < 26; i++) children[i] = 0;\n        memset(children, 0, sizeof(children)); \n    }\n};\n\nclass WordDictionary\n{\npublic:\n    /** Initialize your data structure here. */\n    WordDictionary()\n    {\n        root = new TrieNode();\n    }\n\n    /** Adds a word into the data structure. */\n    void addWord(string word)\n    {\n        TrieNode *node = root;\n        for (char c : word)\n        {\n\t\t\t// if we already have put a specific letter in a specific level, we don\'t need to create another node\n\t\t\t// for example, in \'dog\' and \'dag\', as we have \'d\' in the same position, \n\t\t\t// we can use the same node which store \'d\' to be the parent of \'o\' and \'a\'\n            if (!node->children[c - \'a\'])\n                node->children[c - \'a\'] = new TrieNode();\n            node = node->children[c - \'a\'];\n        }\n\t\t// as we achieved the last node, this will be our leaf node\n        node->is_leaf = true;\n    }\n\n    /** Returns if the word is in the data structure. A word could contain the dot character \'.\' to represent any one letter. */\n    bool search(string word)\n    {\n\t\t// we want a search function which has other parameters, so we\'ll create a private search function\n        return search(word, root, 0);\n    }\n\nprivate:\n    TrieNode *root; // our private root\n\n    bool search(string word, TrieNode *node, int pos)\n    {\n\t\t// in our recursion, first we need to code our stop condition\n        if(pos == word.size())\n            return node->is_leaf;\n       \n\t   // if there\'s no \'.\', we can just iterate in our linked list\n        if (word[pos] != \'.\'){\n            node = node->children[word[pos] - \'a\'];\n\t\t\t// this \'node\' before the search is to avoid unnecessary recursion calls (if node is null, the linked list was ended up)\n\t\t\t// we increment our \'pos\' by 1, in order to search the next character, if it exists\n            return node && search(word, node, pos + 1);\n        }\n        \n\t\t// if there\'s a \'.\', we need to force iteration in all possible cases\n        for (int i = 0; i < 26; i++)\n\t\t\t// \'node->children[i]\' is here to avoid unnecessary recursion calls (if this node->children[i] is null, the linked list was ended up)\n            if(node->children[i] && search(word, node->children[i], pos + 1))\n                return true;\n        return false;        \n    }\n};\n```
['Trie', 'C', 'C++']