[C++] Trie-based Approach Explained, ~90% Time, ~70% Space
The core idea is to solve this problem with a Trie, a tree-like structure that allows us to navigate across a vocabulary of possible words, so that its root sto
The core idea is to solve this problem with a [`Trie`](https://en.wikipedia.org/wiki/Trie), a tree-like structure that allows us to navigate across a vocabulary of possible words, so that its root store as `children` all the possible first letters of all the words in the vocabulary and they in turn point to the possible second letters and so on - check the wiki link above for more info and a visual representation.\n\nThe advantages of this approach are clear when you start to think about navigating the tree structure only once to verify if a word is valid: does it start with `\'t\'`? If so, you go down that route, otherwise you do not waste time checking for all the other possible combinations; and for larger vocabularies and/or longer word the difference in performances might be massive.\n\nSo, in order to implement it, first of all we need a base node with at least 2 properties: `children` (ie: all the other nodes that start from there and lead to other words) and a boolean telling us if a word was ending there or not (`eow`, in my code, as in "end of word").\n\nAlso note that since an array can vastly improve performance over a vector, but it is not initialised by default, we will have to do so in our constructor for our trie, `WordDictionary`.\n\nSince we know we will only get lowercase letters and we really want (and love!) to save resources whenever it is possible, our array of pointers is going to be only `26` in size and the helper function `convertChar` will help us turning the characters we get in matching indexes in the `0 - 25` range.\n\nAnd, well, that was the easy part - I am not gonna lie here -, but if you grasp it properly, the rest is definitely going to come down much more easily.\n\nSo we also need to implement the `add` method that will gradually populate our trie, building graphs out of new words: we loop through each character, check if we already have a matching node for it in the current `children`, we create one if not and we update our pointer `root` until we are done, being mindful of setting `eow` to `true` for the last word, without touching it otherwise: if for example we add, in order `"pip"` and `"pippi"`, we will have `eow` set to `true` for both the second `\'p\'` and the second `\'i\'` nodes.\n\nAnd that was the intermediate part, so now catch your breath and be ready for the hard part (including looking for wild card characters, the real challenge of this kata): the `search` method is meant to take initially just one `word`, but we might be better off allowing it to receive different optional parameters too: an `index` of where to start to look in the string (defaulted to `0`) and its companion `*WordDictionary` pointer `root` telling us what tree to use for our search (defaulted to `this`).\n\nLet\'s start with the hardest part: when the character is `\'.\'`, the wild card option, we do not proceed through a child linearly, but we ask our Trie to check for all the children: we return `any_of` taking all of them and returning `false` first of all if the node is not there (meaning: no child present and no letter matches that path), otherwise we return `true` if either `node->eow` (it is a valid, end of word) and `i == word.size() - 1` (it is actually the last character).\n\nAlternatively, we just invoke search recursively (still provided `node` exist, otherwise we would be using `root` at each call and I had to debug a bit before noticing that!): same string, increased `index`, updated `root`.\n\nThe other cases are a bit easier: if we find a character matching no element in the current `children`, we return false; otherwise we update `root` to be `root->children[c]` and we either return when it is the last character or proceed with the next iteration of the query string.\n\nIf all else fails, we just return `false` :)\n\nThe code:\n\n```cpp\nclass WordDictionary {\npublic:\n    WordDictionary *children[26];\n    bool eow = false;\n    /** Initialize your data structure here. */\n    WordDictionary() {\n        // initially setting all children = to NULL\n        for (auto &c: children) c = NULL; \n    }\n    int convertChar(char c) {\n        return c - \'a\';\n    }\n    \n    /** Adds a word into the data structure. */\n    void addWord(string word) {\n        // building a Trie from a word\n        WordDictionary *root = this;\n        for (char c: word) {\n            c = convertChar(c);\n            // if there is not already such a children Trie, we create it\n            if (!root->children[c]) root->children[c] = new WordDictionary;\n            root = root->children[c];\n        }\n        root->eow = 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, int index = 0, WordDictionary *root = NULL) {\n        // in the base call we just take this as a root\n        if (!root) root = this;\n        // looping through all the characters\n        for (int i = index; i < word.size(); i++) {\n            // if a \'.\' is found, we move with a DFS approach across the Trie\n            if (word[i] == \'.\') return any_of(begin(root->children), end(root->children), [this, i, &word](WordDictionary *node){return node && (node->eow && i == word.size() - 1 || i + 1 < word.size() && search(word, i + 1, node));});\n            // otherwise we stop if no child matching the current character is present...\n            int c = convertChar(word[i]);\n            if (!root->children[c]) return false;\n            // update root in any case\n            root = root->children[c];\n            // and check if that was the last character, matching the termination of some Trie\n            if (i == word.size() - 1) return root->eow;\n        }\n        return false;\n    }\n};\n```
['Depth-First Search', 'Trie', 'C', 'C++']