✅C++|| Recursion || Memoization || Very Easy || Approach || Complexity
Intuition\n Describe your first thoughts on how to solve this problem. \nRecursion\n\n# Approach\n Describe your approach to solving the problem. \n- store all 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nRecursion\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n- store all strings in set to find it in fast.\n- traverse on each word\n      - check if it can func(concat) or not\n      - push in ans\n\n\n## concat function\n- traverse on each char of word\n- pick up prefix string \n- check if (curr string (0,idx) is present in set && prefix string is present || call concat function on prefix).\n        - if yes return true\n- after end of loop return false bcz we not find 2 or more words in that word.\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n$$O(exponential)$$\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n$$O(n*max.word.length) + O(n)$$\n\n# Code\n```\nclass Solution {\nprivate:\nbool isConcat(string word,unordered_set<string>& st){\n    int n = word.size();\n    for(int i=1;i<n;i++){\n        string prefix = word.substr(i);\n        if(st.count(word.substr(0,i))&&(st.count(prefix)||isConcat(prefix,st)))return true;\n    }\n    return false;\n}\npublic:\n    vector<string> findAllConcatenatedWordsInADict(vector<string>& words) {\n        if(words.size()==0)return {};\n        unordered_set<string> st;\n        vector<string> ans;\n        for(auto word:words)st.insert(word);\n        for(auto word:words){\n            if(isConcat(word,st))ans.push_back(word);\n        }\n        return ans;\n    }\n};\n```\n# Approach\n<!-- Describe your approach to solving the problem. -->\n- just apply memoization on Upper solution.\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n$$O(n*(max.len.word)^3)$$\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n$$O(n*max.word.length) + O(n)$$\n\n# Code\n\n```\nclass Solution {\nprivate:\nbool isConcat(string word,unordered_set<string>& st,unordered_map<string,bool>& mp){\n    int n = word.size();\n    if(mp.count(word))return mp[word];\n    for(int i=1;i<n;i++){\n        string prefix = word.substr(i);\n        if(st.count(word.substr(0,i))&&(st.count(prefix)||isConcat(prefix,st,mp)))return mp[word] = true;\n    }\n    return mp[word] = false;\n}\npublic:\n    vector<string> findAllConcatenatedWordsInADict(vector<string>& words) {\n        if(words.size()==0)return {};\n        unordered_set<string> st;\n        unordered_map<string,bool> mp;\n        vector<string> ans;\n        for(auto word:words)st.insert(word);\n        for(auto word:words){\n            if(isConcat(word,st,mp))ans.push_back(word);\n        }\n        return ans;\n    }\n};\n```
['Dynamic Programming', 'Recursion', 'Memoization', 'C++']