Simple Recursion and Optimization | Java C++
Intution\nFirst lets approach the easiest ones.\n\n1. Solution 1: a sub problem\n\tThe simple idea is we will break a string into 2  Strings and see if they are
Intution\nFirst lets approach the easiest ones.\n\n1. Solution 1: a sub problem\n\tThe simple idea is we will break a string into 2  Strings and see if they are they are there in the array\n\teg [cat, s, cats]; \n\t\n![image](https://assets.leetcode.com/users/images/719680f5-338f-4d6a-999c-f4e57325c379_1674780347.8472507.png)\n\nHowever the second part need not always be there in the array, but it can aslo be a comination of words, but simple idea is to pass the right part again to function. If left is in dict and right can be formed or is in dict we have a word that can be formed.\n![image](https://assets.leetcode.com/users/images/e4435ad6-2721-4ff6-93e0-7578271f5557_1674780594.4040034.png)\n\nThe approach is simple, we pass the words to canBeformed function and check and then add to result;\n\nFurther optimization\n\nWe are recalculating can be formed for the same word multiple time i.e cat can be passed to canBeformed multiple times. We can simple store already formed words in hashSet\n\nhttps://youtu.be/BThdNPvJrpQ\n\n![upvote.webp](https://assets.leetcode.com/users/images/e81a44ac-2a0a-4268-8033-63780c428560_1674698166.6324708.webp)\n\n\n\tSet<String> dict;\n    Set <String> formedWords;\n    public List<String> findAllConcatenatedWordsInADict(String[] words) {\n        List<String> result = new ArrayList<>();\n        dict = new HashSet<>(Arrays.asList(words));\n        formedWords = new HashSet<>();\n        \n        \n        for(String word:words){\n            if(canbeFormed(word)){\n                result.add(word);\n            }\n        }\n        return result;\n    }\n    \n    public boolean canbeFormed(String s){\n        if(formedWords.contains(s)) return true;\n        \n        for(int i = 1;i<s.length();i++){\n            String s1 = s.substring(0,i);\n            String s2 = s.substring(i);\n            if(dict.contains(s1)){\n                if(dict.contains(s2) || canbeFormed(s2)) {\n                    formedWords.add(s);\n                    return true;\n                }\n            }\n        }\n        return false;\n    }\n\n\n\n```\nunordered_set<string> dict;\nunordered_set<string> formedWords;\npublic:\n    vector<string> findAllConcatenatedWordsInADict(vector<string>& words) {\n   \n    vector<string> result;\n    dict = unordered_set<string>(words.begin(), words.end());\n    formedWords = unordered_set<string>();\n    \n    for (auto word : words) {\n        if (canbeFormed(word)) {\n            result.push_back(word);\n        }\n    }\n    return result;\n}\n\nbool canbeFormed(std::string s) {\n    if (formedWords.count(s)) return true;\n\n    for (int i = 1; i < s.length(); i++) {\n        string s1 = s.substr(0, i);\n        string s2 = s.substr(i);\n        if (dict.count(s1)) {\n            if (dict.count(s2) || canbeFormed(s2)) {\n                formedWords.insert(s);\n                return true;\n            }\n        }\n    }\n    return false;\n}\n```\n\n\n
['C', 'Java']