[C++] Trie-based Linear Approach, ~98% Time, ~35% Space
Typical trie problem, so first of all we need to define a Trie structure - no frills, with just 2 properties:\n children, an array of 26 pointers to other Tries
Typical trie problem, so first of all we need to define a `Trie` structure - no frills, with just 2 properties:\n* `children`, an array of 26 pointers to other `Trie`s (one for each lowercase letter);\n* `eow`, which marks the end of a word.\n\nSome people might have build an `add` method here, but it is kinda unnecessary and just wasteful in terms of memory to have one such method for each instance of this struct.\n\nIn our main function we are then going to create first of all a `res` variable, initially empty, and a base `Trie`, creatively called `trie`, which we will populate passing all the strings and all the characters from all the strings, once.\n\nWe will go down this path, or at least a rather similar one, once more, checking all the strings once we are done and verifying which ones do not have even a single character\'s `eow` flagged as `true` (meaning they would not be built from intermediate partial strings), provided the string we are currently checking is not smaller than `res`, in which case we just `continue` and move to the next string.\n\nIf we meet even just one character with `eow` still set to `false` (default value), we `break` and we move on to the next string.\n\nIf we finish looping all the characters and `eow` is `true` even for the last one (`curr->eow`) and the size of the string `s` is either greater than the size of `res` or if the sizes are the same, but `s < res`, then we update `res` to be the value of `s`.\n\nAt the end of the loop, we return `res`.\n\nThe code:\n\n```cpp\nstruct Trie {\n    Trie *children[26] = {NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL};\n    bool eow = false;\n};\n\nclass Solution {\npublic:\n    string longestWord(vector<string>& words) {\n        string res;\n        // creating and populating a tree structure\n        Trie *trie = new Trie(), *curr;\n        for (string s: words) {\n            curr = trie;\n            for (char c: s) {\n                // normalising c to be in the 0 - 26 range\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        // parsing the trie to find the best longer full matches\n        for (string s: words) {\n            // avoiding unnecessary loops\n            if (s.size() < res.size()) continue;\n            curr = trie;\n            for (char c: s) {\n                // normalising c to be in the 0 - 26 range, again\n                c -= \'a\';\n                curr = curr->children[c];\n                if (!curr->eow) break;\n            }\n            // updating res if it is all matching and s is either longer\n            // or same length and minor in lexicographic order\n            if (curr->eow && (s.size() > res.size() || s.size() == res.size() && s < res)) res = s;\n        }\n        return res;\n    }\n};\n```
['String', 'Depth-First Search', 'Trie', 'C', 'C++']