[C++] Trie vs. Hashmap Solutions Explained, 100% Time (40ms), ~99% Space (30.7MB)
Handbook example of a problem which is desperately screaming "solve me witha trie!" as you even glance to through the code template; and thus we will fulfill th
Handbook example of a problem which is desperately screaming "solve me witha trie!" as you even glance to through the code template; and thus we will fulfill this heartfelt plea.\n\nLet\'s start with declaring our `Trie` class, which will just contain two properties:\n* `eow` will mark if the current node is an end of the word, defaulted to `false`;\n* `children` is an array of `26` `Trie` pointers, defaulted to `NULL`.\n\nIn our class we will define just three variables:\n* `root` and `curr` are `Trie` pointers we will use to handle creation and search of our trie;\n* `res` is a boolean that we will use in our search routine.\n\nIn our constructor, we will just initialised `root` to point to an empty `Trie`.\n\n`addWord` will take a `word` (passed as a reference) and:\n* set `curr` to point initially to `root`;\n* for each character `c`:\n\t* reduce `c` to the `0 - 25` range, subtracting `\'a\'` from it;\n\t* check if we already have `curr->children[c]` and if not, create it as a new node;\n\t* move `curr` to be `curr->children[c]`;\n* set `curr->eow` to `true`, to mark the last node of a word.\n\n\'searchWord` will work more interestingly on the same logic, and we added another parameter to it, `start`, that will default to `0` so that we in this method we can:\n* check for the first base case - when we start looking for a word, we will have to reset `res` to `false` and `curr` to `root`;\n* check if we already found a valid match (ie: `res == true`), in which case we just `return` `res`;\n* check if we are at the end of the word (ie: `start == word.size()`), in which case we just `return` if we are on an ending word node or not (ie: the value of `curr->eow`);\n* if not, we start dealing with the general case and store `word[start]` into `c`;\n* if `c == \'.\'`, we will have to deal with a wild card character, thus we will:\n\t* declare `origCurr` to store the initial value of `curr` here;\n\t* iterate through each `child` in `curr->children` and:\n\t\t* `continue` if `child` is `NULL`;\n\t\t* set `curr` to be `child`;\n\t\t* update `res` to the result of calling `searchWord` with an increaed value of `start`;\n\t\t* check if we already reached a match and thus `break` out of the `loop` if we found it (ie: `res == true`);\n\t* backtrack `curr` to its initial value `origCurr`;\n\t* `return` `res`;\n* for any other character, we will instead decrease `c` again by `\'a\'` to make it fit in our `0 - 25` range;\n* `return` `false` if no child matches `c` in `curr`;\n* update `curr` otherwise to be `curr->children[c]`;\n* `return` the result of  calling `searchWord` with an increaed value of `start`.\n\nThe code:\n\n```cpp\nstruct Trie {\n    bool eow = false;\n    Trie *children[26] = {};\n};\n\nclass WordDictionary {\n    Trie *root, *curr;\n    bool res;\npublic:\n    WordDictionary() {\n        // initialising the trie\n        root = new Trie;\n    }\n    \n    void addWord(const string &word) {\n        // adding word to the trie using curr as a pointer\n        curr = root;\n        for (char c: word) {\n            c -= \'a\';\n            if (!curr->children[c]) curr->children[c] = new Trie();\n            curr = curr->children[c];\n        }\n        curr->eow = true;\n    }\n    \n    bool search(const string &word, int start = 0) {\n        // base case: we start the search and thus set res to false\n        if (!start) {\n            res = false;\n            curr = root;\n        }\n        // base case: we already found a match, so we stop recursing\n        if (res) return res;\n        // base case: we are done parsing the string\n        if (start == word.size()) return curr->eow;\n        // general case:\n        char c = word[start];\n        // wild card character\n        if (c == \'.\') {\n            Trie *origCurr = curr;\n            for (auto child: curr->children) {\n                if (!child) continue;\n                curr = child;\n                res |= this->search(word, start + 1);\n                // stopping if we found a result already\n                if (res) break;\n            }\n            // backtracking curr\n            curr = origCurr;\n            return res;\n        }\n        // any other character\n        c -= \'a\';\n        if (!curr->children[c]) return false;\n        curr = curr->children[c];\n        return this->search(word, start + 1);\n    }\n};\n```\n\nI wanted to go for the lolz and get a quick and dirty solution just mapping words by length first and starting letter later (and in case of queries starting with `\'.\'`, we will go through all the words of the same length of the query).\n\n`matches` is our helper function to handle also wild card characters (in the second string) and the rest is pretty straightforward.\n\nI thought I would get awful performance, but it turns out I went pretty close (52ms in this version vs 40ms in the previous really surprised to see I actually used much less memory this way (30.7MB vs 43MB in the previous version).\n\nI guess I might mitigate a bit for queries starting with `\'.\'` storing words also by their final letter and then picking the smaller vector, but I would definitely burn much more memory and use more time initially to store them, so it would really depend on how this DS is used (longer words, more frequent `\'.\'` inital starting characters, etc.):\n\n```cpp\nclass WordDictionary {\n    unordered_map<int, unordered_map<char, vector<string>>> store;\n    bool matches(const string &s1, const string &s2) {\n        for (int i = 0, lmt = s1.size(); i < lmt; i++) {\n            if (s1[i] != s2[i] && s2[i] != \'.\') return false;\n        }\n        return true;\n    }\npublic:\n    WordDictionary() {}\n    \n    void addWord(const string &word) {\n        store[word.size()][word[0]].push_back(word);\n    }\n    \n    bool search(const string &word) {\n        int wLen = word.size();\n        if (store.find(wLen) == end(store)) return false;\n        char c = word[0];\n        // first case: wild card - checking every single word in that bucket\n        if (c == \'.\') {\n            for (auto &bucket: store[wLen]) {\n                for (auto &item: bucket.second) if (matches(item, word)) return true;\n            }\n            return false;\n        }\n        // second case: generic character\n        if (store[wLen].find(c) == end(store[wLen])) return false;\n        auto &bucket = store[wLen][c];\n        for (auto &item: bucket) if (matches(item, word)) return true;\n        return false;\n    }\n};\n```
['String', 'C', 'C++']