472: Solution with step by step explanation
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\n1. Create a set of all words in the given list.\n2. Define a recursive fu
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n1. Create a set of all words in the given list.\n2. Define a recursive function called isConcat to check if a word is concatenated.\n3. Memoize the isConcat function using the functools.lru_cache decorator to cache its results and improve performance.\n4. For a given word, try all possible splits of the word by iterating over its characters using a for loop.\n5. For each split, get the prefix and suffix of the split using string slicing.\n6. Check if the prefix is in the wordSet.\n7. If the prefix is in the wordSet, check if the suffix is either in the wordSet or can be formed by concatenating other words by recursively calling the isConcat function on the suffix.\n8. If the suffix is either in the wordSet or can be formed by concatenating other words, then the word is concatenated and we can return True from the isConcat function.\n9. If none of the splits result in a concatenated word, then the word is not concatenated and we can return False from the isConcat function.\n10. Use a list comprehension to get all concatenated words by iterating over the words in the input list and calling the isConcat function on each word.\n11. Return the list of concatenated words.\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution:\n    def findAllConcatenatedWordsInADict(self, words: List[str]) -> List[str]:\n        # Create a set of all words in the given list\n        wordSet = set(words)\n\n        # Define a recursive function to check if a word is concatenated\n        @functools.lru_cache(None)  # Memoize the function with least-recently-used cache\n        def isConcat(word: str) -> bool:\n            for i in range(1, len(word)):  # Try all possible splits of the word\n                prefix = word[:i]  # Get the prefix of the split\n                suffix = word[i:]  # Get the suffix of the split\n                if prefix in wordSet and (suffix in wordSet or isConcat(suffix)):\n                    # If the prefix is in the wordSet and the suffix is either in the wordSet\n                    # or can be formed by concatenating other words, then the word is\n                    # concatenated\n                    return True\n            return False\n\n        # Use a list comprehension to get all concatenated words\n        return [word for word in words if isConcat(word)]\n\n```
['Array', 'Dynamic Programming', 'Depth-First Search', 'Python', 'Python3']