[C++] | Trie solution
Intuition\nBy storing the data in a Trie tree structure we will be able to check the presence of the word in O(s) time, where s is the lenghts of the word. As t
# Intuition\nBy storing the data in a Trie tree structure we will be able to check the presence of the word in O(s) time, where s is the lenghts of the word. As the words are relatively short - 30 characters max - this structure allows us to do that very efficiently.\n\n# Approach\n1. Initialize a trie tree\n2. Add elements to the trie tree-> appendToTrie()\n3. For each word check if it can be created by concatenation of shorter words \n\nTo execute step 3 we can follow a simple DFS approach:\n1. If there exists a word that ends in a particular place, run DFS from the root of the tree.\n2. If no words end, go to the next letter of the word in the tree if it exists.\n3. Remember how many words have already ended\n4. Check stop conditions -> if the entire word has been checked or the answer has already been found\n\n# Complexity\n- Time complexity: O(n * s^2)\n \n- Space complexity: O(M)\n\nn - number of words\ns - maximum word length\nM - sum of all word lengths\n\n# Code\n```\nclass Solution {\npublic:\n    struct trieNode {\n        int letters[26];\n        bool end = false;\n    };\n\n    void appendToTrie(vector<trieNode>& trie, int trieIndex, string& word, int wordIndex) {\n        if (word.size() == wordIndex) {\n            trie[trieIndex].end = true;\n            return;\n        }\n        if (trie[trieIndex].letters[word[wordIndex] - \'a\'] == 0) {\n            trie[trieIndex].letters[word[wordIndex] - \'a\'] = trie.size();\n            trie.push_back({});\n        }\n        appendToTrie(trie, trie[trieIndex].letters[word[wordIndex] - \'a\'], word, wordIndex + 1);\n    }\n\n    void checkInTrie(vector<trieNode>& trie, int trieIndex, string& word, int wordIndex, bool& ok, int cnt) {\n        if (word.size() == wordIndex && trie[trieIndex].end && cnt > 0)\n            ok = true;\n        if (ok)\n            return;\n        if (word.size() == wordIndex)\n            return;\n        if (trie[trieIndex].end)\n            checkInTrie(trie, 0, word, wordIndex, ok, cnt + 1);\n        if (trie[trieIndex].letters[word[wordIndex] - \'a\'])\n            checkInTrie(trie, trie[trieIndex].letters[word[wordIndex] - \'a\'], word, wordIndex + 1, ok, cnt);\n    }\n\n    vector<string> findAllConcatenatedWordsInADict(vector<string>& words) {\n        vector<trieNode> trie;\n        trie.push_back({});\n\n        for (auto word : words) \n            appendToTrie(trie, 0, word, 0);\n\n        vector<string> ans;\n\n        for (auto word : words) {\n            bool ok = false;\n            checkInTrie(trie, 0, word, 0, ok, 0);\n            if (ok)\n                ans.push_back(word);\n        }\n\n        return ans;\n    }\n};\n```
['Depth-First Search', 'Trie', 'C++']