Clean Codes🔥🔥|| Full Explanation✅|| Trie & DFS✅|| C++|| Java || Python3
Intuition :\n- We can use the data structure trie to store the words. Then for each word in the list of words, we use depth first search to see whether it is a 
# Intuition :\n- We can use the data structure trie to store the words. Then for each word in the list of words, we use depth first search to see whether it is a concatenation of two or more words from the list.\n\n- We first build a trie structure that stores the list of words. In every trie node, we use an array of length 26 to store possible next trie node, and a flag to indicate whether the trie node is the last letter of a word in the dictionary.\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach :\n- Suppose we have a list of words like this, words = [\u201Ccat\u201D, \u201Ccats\u201D, \u201Ccatsdogcats\u201D, \u201Cdog\u201D, \u201Cdogcatsdog\u201D, \u201Chippopotamuses\u201D, \u201Crat\u201D, \u201Cratcatdogcat\u201D]. The trie structure we build looks like the following. If the node is an end of a word, there is a * next to it.\n```\n    c    d    h    r\n    |    |    |    |\n    a    o    i    a\n    |    |    |    |\n    t*   g*   p    t*\n    |    |    |    |\n    s*   c    p    c\n    |    |    |    |\n    d    a    o    a\n    |    |    |    |\n    o    t    p    t\n    |    |    |    |\n    g    s    o    d\n    |    |    |    |\n    c    d    t    o\n    |    |    |    |\n    a    o    a    g\n    |    |    |    |\n    t    g*   m    c\n    |         |    |\n    s*        u    a\n            |    |\n            s    t*\n            |\n            e\n            |\n            s*\n```\n- Next, for each word in the sentence, we search whether the word is a concatenation of two or more other words from the list. We can use depth first search here.\n\n- For each word, we start from the root node of the trie and the first letter of the word. If the letter is not null in the current trie node, we go to the next trie node of that letter. We keep searching until the trie node is an end of a word (with a * in the above graph). \n\n- We increase the count of words the comprise the current word. Then we start from the root node of the trie again, and keep on searching until we reach the end of the current word. If we cannot find the letter in the trie, we go backtrack to the last run of trie nodes and continue the search.\n\n- If we can find a concatenation of words that reaches the end of the current word, we check how many words are concatenated. If it is greater than 2, we put the current word to the final answer\n<!-- Describe your approach to solving the problem. -->\n\n# Please Upvote\uD83D\uDC4D\uD83D\uDC4D\n```\nThanks for visiting my solution.\uD83D\uDE0A\n```\n# Codes for above Explained Approach :\n```C++ []\nclass Solution {\nstruct TrieNode {\n    TrieNode* arr[26];\n    bool is_end;\n    TrieNode() {\n        for (int i = 0; i < 26; i ++) arr[i] = NULL;\n        is_end = false;\n    }  \n};\n\nvoid insert(TrieNode* root, string key) {\n    TrieNode* curr = root;\n    for (int i = 0; i < key.size(); i ++) {\n        int idx = key[i] - \'a\';\n        if (curr->arr[idx] == NULL)\n            curr->arr[idx] = new TrieNode();\n        curr = curr->arr[idx];\n    }\n    curr->is_end = true;\n}\n\nbool dfs(TrieNode* root, string key, int index, int count) {\n    if (index >= key.size())\n        return count > 1;\n    TrieNode* curr = root;\n    for (int i = index; i < key.size(); i ++) {\n        int p = key[i] - \'a\';\n        if (curr->arr[p] == NULL) {\n            return false;\n        }\n        curr = curr->arr[p];\n        if (curr->is_end) {\n            if (dfs(root, key, i+1, count+1))\n                return true;\n        }\n    }\n    return false;\n}\npublic:\nvector<string> findAllConcatenatedWordsInADict(vector<string>& words) {\n    TrieNode* root = new TrieNode();\n    for (int i = 0; i < words.size(); i ++) {\n        insert(root, words[i]);\n    }\n    vector<string> ans;\n    for (int i = 0; i < words.size(); i ++) {\n        if (dfs(root, words[i], 0, 0))\n            ans.push_back(words[i]);\n    }\n    return ans;   \n}\n};\n```\n```Java []\nimport java.util.List;\nimport java.util.ArrayList;\n\nclass Solution {\n    class TrieNode {\n        TrieNode[] arr = new TrieNode[26];\n        boolean is_end;\n        TrieNode() {\n            for (int i = 0; i < 26; i ++) arr[i] = null;\n            is_end = false;\n        }  \n    };\n\n    void insert(TrieNode root, String key) {\n        TrieNode curr = root;\n        for (int i = 0; i < key.length(); i ++) {\n            int idx = key.charAt(i) - \'a\';\n            if (curr.arr[idx] == null)\n                curr.arr[idx] = new TrieNode();\n            curr = curr.arr[idx];\n        }\n        curr.is_end = true;\n    }\n\n    boolean dfs(TrieNode root, String key, int index, int count) {\n        if (index >= key.length())\n            return count > 1;\n        TrieNode curr = root;\n        for (int i = index; i < key.length(); i ++) {\n            int p = key.charAt(i) - \'a\';\n            if (curr.arr[p] == null) {\n                return false;\n            }\n            curr = curr.arr[p];\n            if (curr.is_end) {\n                if (dfs(root, key, i+1, count+1))\n                    return true;\n            }\n        }\n        return false;\n    }\n    public List<String> findAllConcatenatedWordsInADict(String[] words) {\n        TrieNode root = new TrieNode();\n        for (int i = 0; i < words.length; i ++) {\n            insert(root, words[i]);\n        }\n        List<String> ans = new ArrayList<String>();\n        for (int i = 0; i < words.length; i ++) {\n            if (dfs(root, words[i], 0, 0))\n                ans.add(words[i]);\n        }\n        return ans;   \n    }\n}\n```\n```Python3 []\nclass TrieNode:\n    def __init__(self):\n        self.children = [None] * 26\n        self.is_end = False\n\nclass Solution:\n    def __init__(self):\n        self.root = TrieNode()\n        \n    def insert(self, root, key):\n        curr = root\n        for i in range(len(key)):\n            idx = ord(key[i]) - ord(\'a\')\n            if not curr.children[idx]:\n                curr.children[idx] = TrieNode()\n            curr = curr.children[idx]\n        curr.is_end = True\n\n    def dfs(self, root, key, index, count):\n        if index >= len(key):\n            return count > 1\n        curr = root\n        for i in range(index, len(key)):\n            p = ord(key[i]) - ord(\'a\')\n            if not curr.children[p]:\n                return False\n            curr = curr.children[p]\n            if curr.is_end:\n                if self.dfs(root, key, i+1, count+1):\n                    return True\n        return False\n\n    def findAllConcatenatedWordsInADict(self, words):\n        for i in range(len(words)):\n            self.insert(self.root, words[i])\n        ans = []\n        for i in range(len(words)):\n            if self.dfs(self.root, words[i], 0, 0):\n                ans.append(words[i])\n        return ans\n```\n# For the 42/43 test case passing issue in C++ : Use this code\n```\nclass Solution {\nprivate:\n    struct Trie\n    {\n        vector<Trie*> children{26};\n        bool end{false};\n    };\n    \n    Trie* root;\n    \n    void insert(string& s)\n    {\n        if (s.empty()) return;\n        Trie* cur = root;\n        for (char c:s)\n        {\n            if (cur->children[c-\'a\'] == nullptr)\n                cur->children[c-\'a\'] = new Trie();\n            cur = cur->children[c-\'a\'];\n        }\n        cur->end = true;\n    }\n    \n    bool dfs(Trie* root, Trie* node, string& word, int idx, int count)\n    {\n        if (!node)\n            return false;\n        \n        if (idx >= word.size())\n        {\n            if (node->end && count >=1 )\n                return true;\n            else\n                return false;\n        }\n        \n        if (node->end && dfs(root, root, word, idx, count+1))\n            return true;\n        return dfs(root, node->children[word[idx]-\'a\'], word, idx+1, count);\n    }\n    \npublic:\n    vector<string> findAllConcatenatedWordsInADict(vector<string>& words) {\n        sort(words.begin(), words.end(), [](const string& w1, const string& w2) {\n            return w1.size() < w2.size();\n        });\n        \n        vector<string> ret;\n        root = new Trie();\n        \n        for(auto &w: words)\n        {\n            if (w.empty()) continue;\n            if(dfs(root, root, w, 0, 0)) \n                ret.push_back(w);\n            else \n                insert(w);\n        }\n    \n        return ret;\n    }\n};\n```\n# Please Upvote\uD83D\uDC4D\uD83D\uDC4D\n![ezgif-3-22a360561c.gif](https://assets.leetcode.com/users/images/72a4b9ca-318a-44de-8711-814663986266_1674788273.972068.gif)\n\n
['Trie', 'Python', 'C++', 'Java', 'Python3']