Day 27 || Simple Recursion - DFS || Easiest Beginner Friendly Sol
Intuition of this Problem:\nWe can solve this problem using various methods:\n- Trie data strucutre\n- dynamic programming\n\nBut I solved this problem using si
# Intuition of this Problem:\nWe can solve this problem using various methods:\n- Trie data strucutre\n- dynamic programming\n\nBut I solved this problem using simple recursion - dfs.\n![WhatsApp Image 2023-01-27 at 7.35.18 AM.jpeg](https://assets.leetcode.com/users/images/d47869df-216b-4184-a650-00035a86e96c_1674785146.2162044.jpeg)\n\n\n<!-- Describe your first thoughts on how to solve this problem. -->\n**NOTE - PLEASE READ APPROACH FIRST THEN SEE THE CODE. YOU WILL DEFINITELY UNDERSTAND THE CODE LINE BY LINE AFTER SEEING THE APPROACH.**\n\n# Approach for this Problem:\n1. Create an empty set \'s\' to store all the words in the given array of strings.\n2. Iterate through the array of strings and insert each word into the set \'s\'.\n3. Create an empty vector \'concatenateWords\' to store all the concatenated words.\n4. Iterate through the array of strings again, for each word, check if it is a concatenated word using the function \'checkConcatenate(word)\'.\n5. In the \'checkConcatenate(word)\' function, use a for loop to iterate through each substring of the word, starting from index 1 to the second last index of the word.\n6. For each substring, check if the prefix and suffix of the substring exists in the set \'s\'.\n7. If the prefix and suffix both exist in the set \'s\', then return true, indicating that the word is a concatenated word.\n8. If the function \'checkConcatenate(word)\' returns true, then insert the word into the \'concatenateWords\' vector.\n9. Return the \'concatenateWords\' vector.\n<!-- Describe your approach to solving the problem. -->\n\n\n# Code:\n```C++ []\nclass Solution {\npublic:\n    set<string> s;\n    bool checkConcatenate(string word) {\n        for(int i = 1; i < word.length(); i++) {\n            string prefixWord = word.substr(0, i);\n            string suffixWord = word.substr(i, word.length()-i);\n            if(s.find(prefixWord) != s.end() && (s.find(suffixWord) != s.end() || checkConcatenate(suffixWord)))\n                return true;\n        }\n        return false;\n    }\n    vector<string> findAllConcatenatedWordsInADict(vector<string>& words) {\n        vector<string> concatenateWords;\n        for(string word : words)\n            s.insert(word);\n        for(string word : words) {\n            if(checkConcatenate(word) == true)\n                concatenateWords.push_back(word);\n        }\n        return concatenateWords;\n    }\n};\n```\n```Java []\nclass Solution {\n    public List<String> findAllConcatenatedWordsInADict(String[] words) {\n        Set<String> s = new HashSet<>();\n        List<String> concatenateWords = new ArrayList<>();\n        for(String word : words)\n            s.add(word);\n        for(String word : words) {\n            if(checkConcatenate(word, s) == true)\n                concatenateWords.add(word);\n        }\n        return concatenateWords;\n    }\n    public boolean checkConcatenate(String word, Set<String> s) {\n        for(int i = 1; i < word.length(); i++) {\n            String prefixWord = word.substring(0, i);\n            String suffixWord = word.substring(i, word.length());\n            if(s.contains(prefixWord) && (s.contains(suffixWord) || checkConcatenate(suffixWord, s)))\n                return true;\n        }\n        return false;\n    }\n}\n\n```\n```Python []\nclass Solution:\n    def findAllConcatenatedWordsInADict(self, words: List[str]) -> List[str]:\n        s = set()\n        concatenateWords = []\n        for word in words:\n            s.add(word)\n        for word in words:\n            if self.checkConcatenate(word, s) == True:\n                concatenateWords.append(word)\n        return concatenateWords\n    def checkConcatenate(self, word: str, s: set) -> bool:\n        for i in range(1, len(word)):\n            prefixWord = word[:i]\n            suffixWord = word[i:]\n            if prefixWord in s and (suffixWord in s or self.checkConcatenate(suffixWord, s)):\n                return True\n        return False\n\n```\n\n# Time Complexity and Space Complexity:\n- Time complexity: **O(n^2*m)** //where n is the number of words in the input array and m is the average length of the words.\n\nThe checkConcatenate() function is called for each word in the input array, and for each call, it iterates through the word to check for possible concatenation, which takes O(m) time. The find() function of the set data structure takes O(log(n)) time on average. So, the total time complexity of the checkConcatenate() function is **O(n*m*log(n))**. Since this function is called for each word in the input array, the total time complexity of the findAllConcatenatedWordsInADict() function is **O(n^2*m*log(n))**.\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: **O(n*m)** //where n is the number of words in the input array and m is the average length of the words.\n\nThe space complexity **O(nm)**, where n is the number of words in the input array and m is the average length of the words. The set data structure is used to store all the words in the input array, which takes O(nm) space.\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nReference Video Link - https://www.youtube.com/watch?v=RLc0SyvDjrI
['Depth-First Search', 'Python', 'C++', 'Java']