JAVA | Simple Recursion | Explained ✅
---\n# Please Upvote \uD83D\uDE07\n---\njava []\nclass Solution {\n    // globally declare a hashset to store all the words \n    private Set<String> set = new 
---\n# Please Upvote \uD83D\uDE07\n---\n``` java []\nclass Solution {\n    // globally declare a hashset to store all the words \n    private Set<String> set = new HashSet<>();\n    public List<String> findAllConcatenatedWordsInADict(String[] words) {\n        // add the words to the set\n        for (String w : words) {\n            set.add(w);\n        }\n\n        // initialise answer arraylist\n        List<String> ans = new ArrayList<>();\n        // iterate over words[]\n        for (String w : words) {\n            if (isConcat(w)) {  // if the method returns a true,\n                ans.add(w);     // we add the word to answer list\n            }\n        }\n\n        return ans;\n    }\n\n    // this method tells us if the word is a concatenation of other words\n    private boolean isConcat(String s) {\n        // we will partition the word into 2 words\n        for (int i = 0; i < s.length(); i++) {\n            String prefix = s.substring(0, i);  // first part\n            String suffix = s.substring(i);     // second part\n            // if both the parts are present in set means that\n            // the original word is a concatenation\n            // if the prefix is not in set, we will create the next prefix\n            // s = "catsdogcats", we have the prefix "cat" which is not in set\n            // so we would make the next prefix "cats", which is present in set\n            // we are left with "dogcats" as suffix. It is not present in set\n            // (if it were present in set we would have got our answer)\n            // Now we would recusively call isConcat() to partition "dogcats" the way we did "catsdogcats"\n            // it\'ll make further partitions of the suffix and check if the partitions are present in set\n            if (set.contains(prefix) && (set.contains(suffix) || isConcat(suffix))) {\n                return true;    // return true if we find that the word is a concatenation\n            }\n        }\n\n        // no partitioning could create the word, means no concatenation possible\n        return false;   // so return false\n    }\n}\n\n// TC: O(n * k), SC: O(n)\n```\n---\n### Clean solution:\n``` java []\nclass Solution {\n    private Set<String> set = new HashSet<>();\n    public List<String> findAllConcatenatedWordsInADict(String[] words) {\n        for (String w : words) {\n            set.add(w);\n        }\n\n        List<String> ans = new ArrayList<>();\n        for (String w : words) {\n            if (isConcat(w)) {  \n                ans.add(w);    \n            }\n        }\n\n        return ans;\n    }\n\n    private boolean isConcat(String s) {        \n        for (int i = 0; i < s.length(); i++) {\n            String prefix = s.substring(0, i);  \n            String suffix = s.substring(i);    \n            if (set.contains(prefix) && (set.contains(suffix) || isConcat(suffix))) {\n                return true;    \n            }\n        }\n\n        return false;  \n    }\n}\n```\n---\n#### Time complexity: $$O(n * k)$$\n`n` be the number of strings in the `word` array. \n`k`be the length of each individual word in words array.\n#### Space complexity: $$O(n)$$\nWe are creating a hashset and putting all the words (from words array) into it.\n
['String', 'Recursion', 'Java']