[Python] Straightforward brute-force solution without memoization/trie/DFS/BFS
A simple brute-force solution without memoization works for me. The algorithm is straightforward:\n1. Construct a dictionary/hashmap of words to enable O(1) loo
A simple brute-force solution without memoization works for me. The algorithm is straightforward:\n1. Construct a dictionary/hashmap of words to enable O(1) lookup.\n2. For each word, check if the given word is concatenated:\n    - Start with an empty subword\n    - For each character `word[i]` in the given word, append the character to the end of the subword\n    - If you can find the subword in the dictionary of words we previously created, recurse to check if `word[i + 1:]` (the rest of the word) is a concatenated word\n    - Maintain the count of subwords found so far\n    - Recursion terminates when you reach the end of the word and the count of subwords is at least two\n3. Return the list of found concatenated words.\n\nHere is the code for the above algorithm:\n\n```python\nclass Solution(object):\n    def findAllConcatenatedWordsInADict(self, words):\n        """\n        :type words: List[str]\n        :rtype: List[str]\n        """\n        def is_concatenated(word, count):\n            if word == "" and count >= 2:\n                return True\n            \n            subword = ""\n            for i in range(len(word)):\n                subword += word[i] # append char to the end of the subword\n                if subword in self.words_dict:\n                    if is_concatenated(word[i + 1:], count + 1):\n                        return True\n\n            # nothing found at this point\n            return False\n        \n        # construct a dict of words to enable O(1) lookup\n        self.words_dict = dict()\n        for w in words:\n            self.words_dict[w] = True\n        \n        res = []\n        for w in words:\n            if is_concatenated(w, 0):\n                res.append(w)\n        \n        return res\n```
['Recursion', 'Python']